중첩 된 for 루프를위한 Big O

외부 for 루프에 중첩 된 일련의 루프에 대해 Big O 실행 시간을 계산하는 것에 대한 질문이 있습니다. 예를 들어중첩 된 for 루프를위한 Big O

 

for (50,000 times) 
{ 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
    for (n times) 
    { 
     //Do something 
    } 
    for (n-2 times) 
    { 
     //Do something 
    } 
}

외부 루프는 상수, 그래서 그 무시 생각합니다. 다음 계산을하는 것만 큼 쉽습니까?

N + N-2 + N + N-2

2N + 2 (N-2)

4N - 4

O (4N - 4)

O (4N) - -4 상수를 제거한 후

이것이 맞습니까?

감사합니다.

출처

2010-11-28 Tom W

나는 그것이 맞다고 생각하지만, 제거 할 다른 상수가 있습니다. O (4n)은 단지 O (n)입니다. –

이 O (n)이

(당신이 방정식의 "큰"부분이 무엇인지에만 관심이있다, 당신은 상수를 제거)입니다. 만약 1..N에서 루프 I 및 J i..n에서 안에 다른 루프 있었다면

, 그것은 O (N^2) 일 것이다.

출처

2010-11-28 01:01:19

감사합니다. 나는 그것이 사실일지도 모른다라고 생각했다. 그러나 그것은 올바르게 보이지 않았다. 나는 모든 상수가 무시되기 때문에 Big O의 한계를 보여주는 50,000 번의 반복을 가진이 사례를 가정합니다. –

@Tom, 아니요, Big-O는 최악의 시나리오 _scales_를 보여줍니다. 입력 크기를 두 배로하면 알고리즘이 어떻게 실행됩니까? O (n^2)로 실행되는 알고리즘의 경우, 입력을 두 배로하면 최악의 실행 시간은 4 배가됩니다. 50.000 루프는이 방정식에서 취소됩니다. –

감사합니다 ... 지금 이해합니다. –

정확합니다. O(N) 인 네 개의 루프를 추가하는 중입니다. 따라서 4O(N) 일 경우 큰 숫자 인 50, 000이 곱해 지지만 이는 N에 종속되지 않습니다.

출처

2010-11-28 01:52:48 fastcodejava

이것은 O (N)입니다. 그러나이 맥락에서, N에 대해 가지고있는 것에 따라 상수는 알고리즘의 성능에 큰 영향을 줄 수 있습니다.

출처

2010-11-28 02:42:56 Shuo

중첩 된 for 루프를위한 Big O

답변

관련 문제