시간복잡도를 공부하다!

수학 공식에서는 log = log10이지만(10이 생략된 것), 빅오표기법에서는 log = log2이다(2가 생략된 것이다).
즉 log n만큼의 시간복잡도를 가졌다는 것은, log2(n)이라는 말과 동일하다.

n log n의 시간 복잡도와 log n은 전혀 다르다! -> 2n과 n을 똑같이 n으로 생각해도 되는 것과 헷갈릴 수 있지만, 그래프 자체가 다르다

1. O(1)과 같은 복잡도를 지닌 알고리즘은, 무한대로 input이 늘어나더라도 계속해서 O(1)만큼의 복잡도를 지닐 수 있음을 의미한다.(1은 1초가 아니고 단지 개념적인 부분이라 짚고 넘어가자)

예를 들어, 배열을 받아 하나의 index만 가져오는 것은 아무리 많은 input이 들어와도 동일하게 특정 조건만 출력하면 되므로, O(1)만큼의 복잡도를 가지고 있다.

2. O(n)만큼의 복잡도는 n앞에 아무리 큰 숫자가 붙더라도 O(n)만큼의 복잡도를 지닌다고 생각하면 된다. O(100000n)도 O(n)의 복잡도를 가진다. 시간복잡도는 엄청 세세하게 최악의 상황에서 걸린 시간을 계산하는 것이 아니라, 대략적인 흐름을 보는 느낌으로 생각하자! -가장 최악의 상황을 계산하는 것은 맞지만!

예를 들어, O(n)의 복잡도는 n이늘어나는 만큼 복잡도도 늘어나긴 하지만, 기하급수적으로 늘어나는 것이 아니라, n만큼만 복잡도가 증가하는 것을 의미한다. for문을 돌아 n만큼 출력하는 것이 하나의 예시가 될 수 있다. 여기서 주의할 점은 2n만큼 출력하더라도 O(2n)은 결국 O(n)이므로 시간복잡도는 O(n)을 가지게 된다.
--> y=x그래프는 O(n)이고, y=2x그래프는 O(2n)과 비슷한 개념이라 생각하자.

3. O(log n)은 O(log2 n)이다.
   n이 1일때 값은 0이고, 2일때 1, 4일때 2, 8일때 3 16일때 4이다. log n그래프가 증가할 수록 완만한 형태를 띠는 것은 x값의 너비 = n은 숫자가 커질 수록 더 넓어지고 y값 = 결과값은 그와 달리 조금씩 늘어나기 때문이다.

예시로는 1~50까지의 범위에서 숫자 한개를 임의로 고른다면, 고른 숫자를 가장 효과적으로 알 수 있는 방법은, 계속 절반씩 나누어서 질문 하는 것이다(25위인지 아래인지부터 시작!) 그렇게 되면 최악의 경우라도 7번 이상 질문하지 않아도 된다. log n 복잡도는 우선 계속해서 같은 양의 범위를 나누는 것을 의미한다고 기억해두자!(병합정렬, 퀵정렬, 힙정렬 찾아보기!)

4. O(n log n)은 분명히 O(log n)과는 다르다! 훨씬 시간 복잡도가 큰 그래프이다. 기존의 O(n)에 log n을 곱한 공식이니 O(n)보다도 시간 복잡도가 크다고 이야기 할 수 있다.

5. O(n2)