빅 O 표기법 런타임

Question

커다란 O 런타임을 실행하기위한 코드가 주어졌습니다. 누군가 내가 올바른 방향에 있는지 아닌지를 말해 줄 수 있습니까?

//program1 
int i, count = 0, n = 20000; 

for(i = 0; i < n * n; i++) 
{ 
    count++; 
} 

O (n^2)입니까?

//number2 
int i, inner_count = 0, n = 2000000000; 

    for(i = 0; i < n; i++) 
    { 
     inner_count++; 
    } 

이 O (n)입니까?

//number3 
for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < n; j++) 
    { 
     count++; 
    } 
} 

O (n^2)?

//number4 
for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < i; j++) 
    { 
     for(k = 0; k < j; k++) 
     { 
      inner_count++; 
     } 
    } 
} 

O (n^3)입니까?

//number5 
int i, j, inner_count = 0, n = 30000; 

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < i; j++) 
    { 
     inner_count++; 
    } 
} 

O (n^3)입니까?

//number6 
int i, j, k, l, pseudo_inner_count = 0, n = 25; 

for(i = 0; i < n; i++) 
{ 
    for(j = 0; j < i*i; j++) 
    { 
     for(k = 0; k < i*j; k++) 
     { 
      pseudo_inner_count++; 
      for(l = 0; l < 10; l++); 
     } 
    } 
} 

매우 혼란 스럽네요 O (n^3) ??

//number7 

int i, j, k, pseudo_inner_count = 0, n = 16; 

for(i = n; i > 1; i /= 2) 
{ 
    for(j = 0; j < n; j++) 
    { 
     pseudo_inner_count++; 
     for(k = 0; k < 50000000; k++); 
    } 
} 

O (n)? (나는 점점 더 열심히한다.)

//number8 
int i, j, pseudo_inner_count = 0, n = 1073741824; 

for(i = n; i > 1; i /= 2) 
{ 
    pseudo_inner_count++; 
    for(j = 0; j < 50000000; j++); 
} 

O (n^2)?

또 하나의 내가보고 {

int i, wrong_count = 0, n = 200; 

    for(i = 0; i < square(n); i++) 
    { 
     wrong_count++; 
    } 

    printf("%d %d\n", wrong_count, square(wrong_count)); 

    return 0; 
} 

int square(int m) 
{ 
    int i, j = 0; 

    for(i = 0; i < m * m; i++) 
    { 
     j++; 
    } 

    return j; 
} 

절대적으로 아무 생각 사람이를 명확히하고 제가 매우 감사하게 될 것입니다 더 잘 이해하는 데 도움 수 있다면이 없다하지 않았다.

Answer 1

• number5가 O 인 (N^2)
• number6는 (N^6)
• number7가 O 인 (N * logN)
• number8가 O 인 (logN)

O이며

나머지는 올바르게 보입니다.

시도이 N의 함수로서 수행되는 방법 많은 작업을 이해하기 위해 모든 상수 동작이

for (int i = 0; i < 333333333; ++i) { j++; } 

같은

는 사실 O에 (1)

Answer 2

number5 = O (N^2) - 두 번째 루프는 1에서 n보다 작은 수로 이동합니다. 따라서 기본적으로 1..n 또는 O (n)입니다.

number6 = O (n^6) - 두 번째 루프는 n^2이고 세 번째 루프는 n^3 (n * n^2)입니다. 네 번째, 내부 루프는 O (1)이므로 카운트가 아닙니다.

number7 = O (nlog n) - 첫 번째 루프는 O (log2 (n))이고 (인덱스를 2로 나누기 때문에) 두 번째 루프는 O (n) 1..n이고 내부 루프는 n에 의존하지 않기 때문에 다시 O (1)이됩니다.

number8 = O (log n) - 상기와 같은 이유.

나머지는 괜찮습니다.

Answer 3

빠른 추적이 맞으면 5, 6, 7 및 8에 대한 답변이 잘못되었습니다.
아래 라인 (5) 따라서 꼼꼼한 연산이며, 8

1: int i, j, pseudo_inner_count = 0, n = 1073741824; 
2: 
3: for(i = n; i > 1; i /= 2) 
4: { 
5:  pseudo_inner_count++; 
6:  for(j = 0; j < 50000000; j++); 
7: } 

정도의 추적이다 O (1) 큰 뭔가 될 것 같은 3 라인 (6)가 보이는 라인의 검사 및 할당과 같은, 항상 50,000,000 될 것 있기 때문에, 그것은 O의 일정 시간 동작 (1)뿐만 아니라,이 쉘 우리 잎이 고려의 :

1: int i, j, pseudo_inner_count = 0, n = 1073741824; 
2: 
3: for(i = n; i > 1; i /= 2) 
4: { 
5: } 

내가 누군가의 숙제를하는 사업에 아니에요 무료이지만이 작업을 끝내겠다. 줄이는 방법은 log_2 작업에 대해 1에 도달하는 데 걸리는 두 가지 의미를 나누는 것이다. O (log (n))의 런타임