시간 복잡도(Big O)란 무엇인가?

코딩테스트를 준비하면서, 알고리즘에 대한 학습이 부족하다는 걸 깨닫고 공부 시작!👩🏻‍💻

✔️시간 복잡도

데이터 구조의 오퍼레이션 혹은 알고리즘이 얼마나 빠르고, 느린지 측정하는 방식이다. 알고리즘의 속도 측정 방식이다.

1초, 2초와 같은 시간을 측정하는 것이 아니라, 얼마나 많은 단계(steps)가 있는가로 측정한다.

즉, 단계가 적을수록 좋은 것이다.

선형 검색의 시간 복잡도(Linear Time Complexity)는 O(N)이라고 한다.

array데이터 구조에서 10개를 선형검색하면선형 검색하면 10번의 step이 실행되고, 20개를 선형 검색하면 20개의 step이 실행된다.

즉, 인풋값과 step이 비례한다.

만약 for문을 두 번 돌리면 step이 두배가 되니까 O(2N)이 되는 걸까? 아니다. O(N)이다.

Big O는 함수의 디테일까지 신경 쓰지 않는다. 인풋 사이즈에 따라 러프하게 어떻게 작동되는지에 따라 정해진다.

위의 코드는 arr의 배열에 몇개의 요소가 있던 상관없이 1 step으로 끝난다.

인풋이 얼마나 크냐에 상관없이 이 함수는 동일한 수의 스텝이 필요 할 것이다.

이 함수의 시간복잡도는 Constant Time(상수 시간)이라고 할 수 있다.

만약 이렇게 print를 두 번한다면 O(2)가 되는 것일까? 아니다. O(1)이다.

for문이 두번 반복되는 중첩 반복(Nested Loops)이 있을 때 발생한다.

로그 시간(Logarithmic time)

이진 검색 알고리즘 설명할 때 쓰는 것이다.

LInear Time보다는 느리지만, Constant Time보다는 빠르다.

하지만, 정렬되지 않은 배열에서는 사용할 수 없다는 점이 있다

O(1) > O(log n) > O(n) > O(n^2) 순으로 선호된다.

출처

728x90