두 개의 중첩 된 루프 실행 시간

Question

루프에 관한 또 다른 질문이 있습니다. 나는 당신이 n * n 번리스트를 반복하기 때문에 실행 시간이 O (n^2) 인 루프를위한 2 개를 알고있다.

하지만 두 개의 루프가있는 동안은 어떨까요?

While (array1 is not empty) 

    if(~~~) 
     do ~~~ 
    else(~~~) 
     do ~~~ 

    while (array2 is not empty) 

    if(~~~) 
     do ~~~ 
    else(~~~) 
     do ~~~ 

그래서 while 루프는 다른 while 루프 안에 중첩됩니다. 이것은 첫 번째 루프가 n 번 반복되고 두 번째 루프가 n 번 반복되기 때문에 실행 시간이 n^2가됩니까? 어떤 도움이 절실히 받아 들여질 것입니다.

감사합니다.

Answer 1

O (n²)에서 중첩 된 for 루프가 실행됩니다. 이 중 두 개가 순차적으로 실행되는 속도를 결정하는 표기법은 O (2n²)입니다. 두 개의 while 회 돌이를 각각 n 회 실행하는 표기법은 O (2n)입니다.

Answer 2

이 경우 중첩 된 것처럼 보이지 않습니다. if/else로 구분 된 2 개의 루프가 있습니다. 이 경우 O (n)이됩니다.

while 루프가 중첩되어 있고 입력 크기를 기반으로한다면 실제로 O (n^2)가됩니다. 당신이 사용하고있는 루프의 '타입'은 중요하지 않습니다. 오히려 여러분이 크기 n의 입력을 루핑한다는 사실입니다.

Answer 3

while (array1 isn't empty){ 
    while (array2 isn't empty){ 
     //code goes here 
    } 
} 

최초 배열은 n 개의 요소를 가지며, 제 2 어레이는 n 및 m이 동일한 특별한 경우 런타임 인 ​​O (n 개 *의 m)

이 다음은 m 요소가 있으면 O (n 개 * n)도 이때

while (array1 isn't empty){ 
//code 
} 

while (array2 isn't empty){ 
//code 
} 

런타임에서 n이 m과 O (m) m 경우 이상이면 O (N)은 O (N) + O (m)이고 n보다 크거나 같습니다.