간단한 시간 복잡성 O (nlogn)

Question

인터뷰에서 Big O 표기법을 검토 중이며이 문제를 발견했습니다.

for i = 1 to n do: 
    j = i 
    while j < n do: 
    j = 2 * j 

간단한 권리? 외부 루프는 n 개의 단계를 제공합니다. 각각의 단계는 while 루프에 대해 j = i 단계 이후로 log (n-j) 또는 log (n-i)의 할당 단계 j=i의 단일 단계 O (1)을 수행합니다. 나는 시간 복잡성이 O (nlogn) 일 것이라고 생각했지만 대답은 O (n)이다. 여기

해답이다

주행 시간은 대략 다음의 합 : 1 + Σ 로그 (N/I) I 1부터 N까지 Θ (N)이다.

이제 약간 녹슬어졌습니다. log(n/i)의 출처는 무엇입니까? 나는 log(n) - log(i) = log(n/i)을 알고있다. 그러나 나는 우리가 log (n-i) log (n) - log (i)로 기록하지 않는다고 생각했다. 그리고 시간 복잡성은 어떻게 O (nlogn)가 아닌가? 나는 무언가를 놓치고있는 것이 틀림 없다고 확신하지만, 나는 이것을 몇 시간 동안 꼼짝 않고 바라 보았다. 그리고 나는 내 마음을 잃기 시작했다.

출처 : 여기에이 문제 Berkeley CS 170, Fall 2009, HW 1

편집의 소스는 다음과 같습니다 그것에 대해 생각 후 조금 더 그것은 내부 루프의 시간 복잡도는 로그임을 의미가 있습니다 (N/I). 각각의 내부 루프가 n-i 번 실행되지만 각 루프를 두 번 반복합니다. 내부 루프가 항상 0에서 시작한다면 우리는 log (n)을 가졌지 만 우리가 반복 할 필요가없는 루프의 숫자는 log (i)입니다. log (n) - log (i)는 log (n/i)이다.

Answer 1

나는 (N/I) 내부 루프에서 오는 로그를 생각

통지 j = i

내가 = 2

내부 루프를 (N 말할 = 10 할) 때 의미하는 방법

while j < n do: 
    j = 2 * j 

j=2에서 10 2하여 j 개의 multilplies 자체 (따라서 로그) & 숨어에만 실행될 그래서 내부 루프

log base 2 n/i times 나는 시간 내부 루프 대부분 한번만 실행하기 때문에 선형 시간처럼 보이는 코드 & 통해 간단한 I = 10을 실행 한 실행 ickly n=10

값을 넘.

예 : i의 값이 2가 될 때 n보다 크거나 같은 경우, 내부 루프를 두 번 이상 실행하지 않습니다.

그렇다면, N = 10는 내부 루프의 한 실행 i=n/2 (if i=10/2=5)부터 얻을 후 J는 J = 5로 시작하는 루프가 한번 2 & while j < n do: 실패 내부 루프 상태 자체를 승산에서 얻는다.

EDIT : // 수학 : J의 값이 J = 0마다 & 내부 루프 i가 N