이 코드의 런타임 복잡성은 무엇입니까?

-3

이 코드 조각의 런타임 복잡성은 얼마나 될까요? 이 코드는 제대로 동작하기 때문에 런타임 복잡성에 대해서는 약간 혼란 스럽습니다.이 코드의 런타임 복잡성은 무엇입니까?

int Something(int x[]){ 
int i=0; 
for(i=0;i<x.length;i++){ 
    //some code over here 
    i=-1; 
}

루프에 continue 및 break 문이 있기 때문에 이것은 무한 루프가 아닙니다. 그러나 루프의 끝에서 조건 i = -1로 인해 루프가 꽤 반복됩니다.

O (n) 복잡도는 중첩 루프가없고이 코드에 중첩 루프가 없음을 의미합니다. 그러나 나는 이것이 O (n) 일 것이라고 정말로 생각하지 않는다. 또한 중첩 된 루프가 없으므로 O (n^2) 또는 이와 비슷한 것이 아닐 것입니다.

출처

2012-02-25 Ashish Agarwal

메모리 또는 시간을 묻는 중입니까? 'O (n) 복잡성은 중첩 루프가없고이 코드에는 중첩 루프가 없다는 것을 의미합니다. 간단하지 않습니다. '그것도 O (n^2) 나 그 어떤 것도 중첩 된 루프가 없으므로 그렇게되지 않을 것입니다. '- 그렇게 간단한 것은 아닙니다. '반복문에 break와 continue 문이있다. '- 모든 코드를 볼 수 없다면 우리는 어떻게 도와야 하는가? –

중단/계속 조건을 보지 않고는 말하기가 불가능합니다. 나머지 코드를 게시하십시오. –

'i = -1;'이 실행되는 최대 횟수는 무엇입니까? 그것이 언제 실행됩니까 w.r.t. 'i'의 마지막 값? –

현재 형태로이 은 O (무한대)입니다. 결코 멈추지 않을 것입니다.

루프에 break 문이 있으면 전체 코드를 제공해야합니다. 그것 없이는 분석이 불가능합니다.

출처

2012-02-25 11:47:18

나머지 질문을 읽어보십시오. 그것은 멈추다. –

@ 닉 반스 : 나는 그 코멘트를 만들 때 내 대답을 업데이 트했다. –

+1'O (무한대)'는 그것이 멈추는 지 여부에 상관없이 정확하다. –

이 코드의 런타임 복잡성은 무엇입니까?

답변

관련 문제