시간 복잡성 - 지나친 작동?

Question

가능한 경우 연산의 복잡성을 과소 평가할 때 사용할 수 있습니까? 이것은 내가 수업에서 배운 질문이다.

Algorithm Power(n) 
Pre: n :: Integer, n > 0 
i = 1 
while (i < n) 
    print i 
    i = i * 3 
done 

나 자신의 완전히 확실하지 오전과 내가 생각하는 이상-생각하고 질문

단순화하기 전에 시간 복잡도 O (N)는 O (N) = 1이 될 것이다 + (3N +? + 1) i = i * 3이 수행되는 시간은 루프 당 한 번이지만 변수 "i"가 반복 당 가속 속도로 증가하면 실제로 문제가 되는가 아니면 과도하게 생각하는 것입니까?

"I"가속화로 인해 O (log n) 또는 O (n^(1/3)) 라인을 따라 루프가 하나 이상 복잡해지기 때문에 O (n)입니까?

Answer 1

정확하지 않으면 O(n)입니다. 단일 루프 레벨은 루프 카운터 (이 경우 i)가 n에 비례하여 선형 적으로 증가 할 때만 O(n)에 해당합니다. O(log n) 또는 O(n^(1/3))인지 여부에 관해서는 할당을위한 것이므로 알아두면됩니다.