알고리즘 실행 시간

Question

안녕하세요 이것은 시험 리뷰에서 질문입니다. 다음 코드 조각의 실행 시간 (Big-O)을 찾아야합니다.

sum = 0; 
for(i = 0; i < n; i++) 
for(j = 0; j < i * i; j++) 
    for (k = 0; k < j; k++) 
    ++sum; 

O (n^4)라고 생각합니다. 가장 안쪽의 루프는 n으로 실행되고, 두 번째는 n^2로 실행되고, 가장 바깥 쪽은 n 번 실행됩니다. 도와 주셔서 감사합니다.

Answer 1

아니요, O (4)가 아닙니다.

더 좋은 방법은 루프가 실행되는 횟수를 계산하는 것입니다 (실제로는 코드가 수행하는 것입니다).

합 (SUM (SUM (1, K = 0..j), J = 0..i * I), I = 0..N)

= 합 (SUM (J, J = i = 0..n) = sum (i * i * (i * i + 1)/2, i = 0 ... n) 4, i = 0..n)이며, 이는 n^5 정도이다.

중간 루프가 i * i이고 내부 대부분의 루프에 대해 실행 중이기 때문에 여분의 시간을 계산해야합니다.

C에서

++

http://codepad.org/nKJ9IUnt

1 0 
2 0 
3 6 
4 42 
5 162 
6 462 
7 1092 
8 2268 
9 4284 
10 7524 
11 12474 
12 19734 
13 30030 
14 44226 
15 63336 
16 88536 
17 121176 
18 162792 
19 215118 

당신은이 테이블을 사용하고 그 결과는 상수 또는 0 당신은이 5 개 파생 상품을 소요 찾을 때까지 유한 차이 (복용 파생 상품)을 계산할 수

상수 목록을 가지고있다. 즉, 목록은 n^5의 순서입니다.

예를 들어, 두 요소 사이의 각 차이가 상수 인 목록이있는 경우 목록을 선형 함수로 나타낼 수 있습니다. 차이의 차이가 일정하면 quadradic 등이 될 것입니다 (차수/차수로 변환되므로 하위 순서는 중요하지 않습니다).

Answer 2

공식적으로 Sigma 표기법을 사용하면 날카로운 정밀도로 성장의 순서를 추론합니다.

Answer 3

당신은 단순히 생각할 수 있습니다 : 더 조심스럽게 안쪽의 루프에서

In the first loop: i = n 
second loop: j = i*i => j = n^2 
third loop: k = j => k = n^2 
So, the bigO = n * n^2 * n^2 = n^5