시간복잡도

시간복잡도

프로그램 코드에서 연산의 수를 따지는 알고리즘의 성능 평가 척도이다. 직접 코드에서 clock(), time() 같은 함수를 사용해 시간을 측정하는 방법도 있다. 하지만, 알고리즘의 성능이 하드웨어와 여러 환경에 영향을 받으면 정확한 성능평가가 이루어지지 않기 때문에 이론적으로 시간복잡도를 많이 사용한다.

오메가 (Big-Ω)

점근적 하한(아무리 빨라도 이만큼보다 빠르지 않다.) -> 최상의 경우라 생각

세타(Big-θ)

빅오와 오메가의 평균.

빅오(Big-O)

점근적 상한(아무리 느려도 이만큼보다 느리지 않다.) -> 최악의 경우라 생각

빅오에서는 O(2n+4) -> O(n)이다. 그 이유는 그래프에서 O(2n+4)가 input이 증가하면 선형으로 시간이 증가한다는 것을 의미하기 때문에 상수는 버리고 O(n)이라고 쓰는 것이다. 그니까 결국 이 알고리즘은 이만큼 input이 들어오면 이정도 선형 시간 안에 해결이 가능하다..

빅오 예제 : https://dingrr.com/blog/post/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%98%88%EC%A0%9C-15%EC%A2%85

자료구조별 시간복잡도(빅오)