확실 내 복잡도 분석 코드 청크의 큰-O 추정 찾으려

Question

올바른

인 경우 I 만든

int a[][] = new int[m][n]; 
int w = 0; 
for (int i = 0; i<m; i++) { 
    for(int j = 0; j<n; j++) { 
     if (a[i][j]%2 == 0) { 
      w++; 
     } 
    } 
} 

esimation 단순화 : O (m) O (없음) O (1) =을 > O (Mn)은

는 모든 경우처럼 보이는 것이다 수 O (MN)가 O (1)이 동작이 정확하고, 실행인지 아닌지는 중요하지 않기 때문에? 아니면 최고/최악/평균 사례가 있습니까?

어떤 통찰력을 감사합니다!

그것은 여기 O(mn) 당신

Answer 1

감사 때문에이 개 루프 (의 서로 중첩되는)의. O (1)은 여기에서 의미가 없습니다. if은 포함되지 않습니다. 두 개의 루프에 대한 전체 탐색에는 영향을주지 않으므로 중단되지 않습니다. if이 흐름을 변경하거나 w를 증가하는 것은 어쨌든에서 루프에 영향을하지 않습니다 다시 때문에, 여기에는 가장 나쁘이 없습니다.

Answer 2

예이 항상있을 것입니다 O (백만)이 운영 등의 시험 조건을 계산하면 몸이 실행 여부 될 경우 때문에 그때는 중요하지 않습니다.

그것은 단지 일정한 O (백만 * 1/2)하지만 2 단지 일정하기 때문에 당신이 그것을 무시할 수있을 것이다.

Answer 3

제공된이 코드에서는 중첩 루프에 상한이 없기 때문에 big-Theta 함수를 사용하지 않고 대신 big-Theta를 사용하여 시간 복잡도를 설명합니다. θ (nm)는 알고리즘이 항상 θ (nm) 시간이 걸리고 여기에 최상/평균/최악의 경우가 없음을 의미합니다.