https://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly
What does O(log n) mean exactly?
I am learning about Big O Notation running times and amortized times. I understand the notion of O(n) linear time, meaning that the size of the input affects the growth of the algorithm proportion...
stackoverflow.com
logn는 한 가지의 선택이 이루어질때마다 다른 선택들의 반을 지운다. 그것은 다음 연산이 1/2로 줄어든다는 걸 의미한다.
https://ageek.dev/big-o-notation
Big-O Notation | AGEEK
Big-O notation gives you a rough indication of the running time of an algorithm and the amount of memory it uses
ageek.dev
반복할 때 마다 데이터의 양을 반으로 줄인다. (이진 검색 알고리즘/ 원문:: binary search)
log n 자체는 이곳에 이진 검색 알고리즘을 예시로 잘 나와 있다.
https://www.youtube.com/watch?v=6Iq5iMCVsXA
for(i = 1; i < n; i *= 2)
위 코드의 시간복잡도는?
라고 물었을때 i *= 2를 어떻게 생각해야 할까?
i *= 2는 다음과 같은 방식으로 변화한다
1, 2, 4, 8, 16 ...
위 코드와 O(n)을 비교해보자.
O(n)이었다면
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16...
이런 식으로 변화하고 있었을 것이다.
그러나 i *= 2라는, 2를 곱한 형태로 변화하고 있다는 건
곧 다음에 출력할 수의 선택을 2분의 1로 줄인다는 소리와 같다.
O(n)이었다면
1, 2, 3, 4를 출력했어야 하는 걸
4만 출력하게 만들었다.
아래로 내려갈 수록 건너뛴 숫자의 양은 점차 커진다.(1, 2, 4... 2의 배수)
그래서 log n으로 나타낼 수 있는 것이다.