시간 복잡도 O (N) 또는 O (Log N)입니까?

i = 1; 
while(i<N) { 
    i*=2; 
}

위의 코드의 시간 복잡성은 O (N)라고 생각하지만 확실하지 않습니다. O (Log N) 및 그 이유를 생각하면 알려 주실 수 있습니까?시간 복잡도 O (N) 또는 O (Log N)입니까?

2016-10-16 snapGeek

정답은 https://stackoverflow.com/questions/48076176/time-complexity-and-integer-inputs/48076437#48076437 – libik

-1

Misread i * = 2 (i + 2).

그냥 O (N)입니다. 정확하게 O (N/2)가됩니다.

왜 이것이 O (log N)가 될 것이라고 생각하십니까?

2016-10-16 01:54:46

입니다. 다음 코드의 경우 O (log N)입니다. (int i = 1; i <= n; i = i * 2)에 대해 에 대해 (int i = 1; i snapGeek

O (log 인쇄 "hello"; http://stackoverflow.com/questions/2307283/what-does-olog-n-mean-exactly – snapGeek

주기 복잡도는 사이클 수에 비례합니다. 그리고 사이클 수는 정확히 Log(N)/Log(2)과 같습니다. 여기서 Log는 대수입니다. 또는 단지 Log2(N)입니다. 여기서 Log2는 밑이 2 인 대수입니다. 따라서 O (Log N)입니다.

2016-10-16 02:00:18

이 답변은 부분적으로 정확합니다 : https://stackoverflow.com/questions/48076176/time -complexity-and-integer-inputs/48076437 # 48076437 – libik

예 : N = 10 루프는 1, 2, 4, 8, 16 (5 회)

는 N 배로하는 경우, N = 20는이 있다면 시간 복잡도는 두배 예상 실행하면서 에). 그러나 해당 루프는 1, 2, 4, 8, 16, 32 (6 회) 실행됩니다.

그리고 다시 N = 40 루프가 1, 2, 4, 8, 16, 32, 64 시간)

N이 클수록 시간 복잡도가 감소하기 때문에 이것은 O (log N)입니다.

2016-10-16 02:00:20

답변