코드 조각의 복잡성 분석

Question

A를 0과 1을 갖는 배열 [1..n]이라고하고, func()은 복잡성이 세타 (m) 인 함수 여야합니다. 주어진 의사 코드에 대해 복잡 할까? 나에게 함수 func에 대한 최악의 경우를 Accorlding

counter=0; 
    for(i=0;i<n;i++) 
     { 
      if(a[i]==1) 
      counter++; 
     else 
      func(); 
    } 

()는 배열이 completly 제로로 가득 할 때이 될 것입니다 대부분의 n 배 호출 할 수 있습니다. func()의 theta noation은 theta (m)로 주어진다.

위의 코드의 복잡성은 다음과 같다 : theta (mn) .... ??? 그렇지 않다면 적절한 확인을 도와주세요.

Answer 1

위의 코드의 시간 복잡도는 O (mn) (Big O mn)이됩니다.
왜?
FUNC() 당신이 말한대로입니다 세타 (m) 시간 복잡성을 계산할 때 자신을 언급 한 바와 같이 지금의 최악의 경우가 FUNC가 호출 n 번는 O (백만)을 초래할 것이다 때.
왜 Theta (mn)이 아닌가요?
쎄타는 시간 복잡성에 더 엄격한 경계입니다. 그것은 항상 최악의 mn *을 수행 할뿐만 아니라 최고 mn * (* 곱하기 또는 상수를 제공하거나 가져옴)을 의미합니다. 따라서 입력에 비례하여 증가합니다. 그러나 오메가 (mn)의 하한 (a.k.a 오메가)을 보장 할 수는 없습니다.
Go here to find more information on big O vs vs Big Theta

그리고 왜 우리는 세타 (mn)의 하한선을 직접 보장 할 수 없습니까?

최저

, Digvijay