큰 O 표기법 숙제-코드 조각 조각 알고리즘 분석? [닫은

StackOverflow https://stackoverflow.com/questions/216796

  •  03-07-2019
  •  | 
  •  

문제

숙제를 위해, 나는 다음 8 개의 코드 조각을 분석하고 달리기 시간에 대해 큰 OH 표기법을 제공했습니다. 내가 올바른 길을 가고 있는지 말해 줄 수 있습니까? 

//Fragment 1
for(int i = 0; i < n; i++)
    sum++;

나는 조각 1에 대해 o (n)을 생각하고있다

//Fragment 2
for(int i = 0; i < n; i+=2)
    sum++;

조각 2의 경우 O (n)

//Fragment 3
for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

조각 3의 경우 O (n^2)

//Fragment 4
for(int i = 0; i < n; i+=2)
    sum++;
for(int j = 0; j < n; j++)
    sum++;

조각 4의 경우 O (n)

//Fragment 5
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

O (n^2) Fragment 5의 경우 N * N이 나를 조금 버리고 있으므로 확실하지 않습니다.

//Fragment 6
for(int i = 0; i < n; i++)
    for( int j = 0; j < i; j++)
        sum++;

O (n^2) 조각 6의 경우

//Fragment 7
for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        for(int k = 0; k < j; k++)
            sum++;

o (n^3) 조각 7의 경우, 그러나 다시 한 번 n * n은 나를 버리고 있습니다.

//Fragment 8
for(int i = 1; i < n; i = i * 2)
    sum++;

조각 8의 경우 O (n)

도움이 되었습니까?

해결책

나는 Fragment 5가 O (n^3)이고, 유사하게 단편 7은 O (n^5)*라고 생각합니다. 또한 조각 8의 경우 O (log (n))처럼 보입니다.

N * N 문제의 경우 루프 N * N 시간의 본문을 실행해야하므로 O (N^2)이면 다른 코드의 순서로 복합적으로 복합합니다. Fragment 8은 실제로 카운터를 증가시키는 대신 두 배로 늘리므로 문제가 클수록 추가 작업이 적을수록 O (log (N))입니다.

*편집하다: 조각 7은 이전에 생각했듯이 O (n^4)가 아닌 O (n^5)입니다. 이것은 둘 다 j입니다 그리고 k 1에서 n * n으로 이동하십시오. 죄송합니다. 이전에 이것을 잡지 못했습니다.

다른 팁

조각 7은 현재 허용 된 의견이 주장하는 것처럼 O (n^4)가 아닌 O (n^5)입니다. 그렇지 않으면 맞습니다.

CASE 8의 경우 N의 일부 값에 대한 반복 수를 기록하고 패턴이 어떻게 보이는지 확인하십시오 ... O (N)

당신은 올바른 길을 가고있는 것 같습니다. n*n과 관련하여 어떤 영향을 미치는가? N의 또 다른 요인이므로 더 높은 순서 일 것입니다.

단지 경고, 나는 이와 같은 다른 게시물을 보았고 그것은 극도로 투표했다. 조심하세요. 여기 게시물입니다.

당신은 올바른 길을 가고 있지만 여기에 상황이 어떻게 더 명확 해지는 지에 대한 팁이 있습니다. 코드가 있다고 가정합니다.

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

그렇습니다. 다른 수준의 코드가 있다는 사실을 고려하십시오. 이 예에서는 지금까지 3 레벨 만 볼 수 있습니다.

  1. 0-n에서 발생하는 외부 루프
  2. 0-100에서 나오는 또 다른 for 루프
  3. 내부의 일부 코드는 표시됩니다 ...

1시에 모든 것을 계산하려고 시도해야합니다. 이것은 대부분의 초보자가 어떤 종류의 산술 오류를하는 곳입니다. 각 레벨에 대해 개별적으로 계산 한 다음 모두 함께 곱하십시오.

행운을 빕니다!

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top