내부 루프의 시간 복잡도

Question

다음 프로그램의 시간 복잡도에 대한 질문이 있습니다. 나는 왜 첫 번째 for 루프가 n + 2인지 두 번째 for 루프는 왜 (n + 1)/2인지를 안다.

// 가 //이 그냥 루프 시간 복잡도 분석을위한 완전히 코딩 프로그램이 아닙니다 루프 샘플

for (int i=n; i>=0; i--) //n + 2 
    for (int j=i; j<n; j++) // (n+2)(n+1)/2 
     cout << i << “,” << j <<endl; //(n+1)(n)/2 

Answer 1

내부 루프는 n-i 번 실행; 즉 i==n 일 때 0 번 실행하고 i == n-1 일 때 1 번, n 번까지 i == 0 일 때까지 실행됩니다. 총 n*(n+1)/2 번. (아니 귀하의 의견에 명시된 (n+1)*(n+2)/2). (당신이 상태로하지 n+2) 내부 루프가 n+1 번 시작되기 때문에

, 그것은 실행 시간의 평균 수 n/2이라고 말할 공정이다.

Answer 2

첫 번째 루프는 시간 복잡성이 O (n)이고 중첩 루프 법선은 O (n^2)의 시간 복잡성을 갖지만 내부 루프는 i의 각 값에 대해 i 번 실행됩니다. 외부 루프가 실행 N 번, 따라서이 같은 실행의 패턴을 볼 수있다 : 1 + 2 + 3 + 4 + ... + n 회

특정 정보 :

1. O (1) : 루프 (loop), 재귀 (recursion)를 포함하지 않고 임의의 다른 일정하지 않은 시간 함수를 호출하면 함수 (또는 명령문 집합)의 시간 복잡도는 O (1)로 간주되어 으로 간주됩니다.

2. O (n) : 루프 변수가 일정한 양만큼 감소 된 경우 루프 변수가 0 (n)으로 간주됩니다. 예를 들어 함수 다음에 O (n) 시간 복잡도가 있습니다.

3. O (n^c) : 중첩 루프의 시간 복잡도는 가장 안쪽 명령문이 실행 된 횟수와 같습니다.

소스 - 포함 i의 현재 값을 1부터 1 N-i 및 j이 반복되는>Link

Answer 3

, N+1 의해 측정 N의 사각형의 절반을 탐색 같이 대각선 분할 . 이를 이해하려면 종이에 직접 테이블을 그려 넣으십시오 : 행에 i, 열에 j, 중첩 루프가 방문하는 각 셀의 눈금.

Answer 4

for 루프의 시간 복잡도는 O (N^2)입니다.

방금 ​​codereview.stackexchange.com과 비슷한 질문에 답했습니다.

다음은 루프의 복잡도를 보여주는 간단한 프로그램입니다.

#include <iostream> 
using namespace std; 

int main() 
{ 
    const int N = 10; 

    int numTotalOps = 0; 
    for (int i = 0; i < N; ++i) 
    { 
     size_t numOps = 0; 
     for (int j=i; j < N; j++) 
     { 
     cout << i << "," << j << endl; 
     ++numTotalOps; 
     ++numOps; 
     } 
     cout << "\nNumber of operations for i = " << i << ": " << numOps << endl; 
    } 

    cout << "\nNumber of total operations: " << numTotalOps << endl; 
    return 0; 
} 

출력 :

0,0 
0,1 
0,2 
0,3 
0,4 
0,5 
0,6 
0,7 
0,8 
0,9 

Number of operations for i = 0: 10 
1,1 
1,2 
1,3 
1,4 
1,5 
1,6 
1,7 
1,8 
1,9 

Number of operations for i = 1: 9 
2,2 
2,3 
2,4 
2,5 
2,6 
2,7 
2,8 
2,9 

Number of operations for i = 2: 8 
3,3 
3,4 
3,5 
3,6 
3,7 
3,8 
3,9 

Number of operations for i = 3: 7 
4,4 
4,5 
4,6 
4,7 
4,8 
4,9 

Number of operations for i = 4: 6 
5,5 
5,6 
5,7 
5,8 
5,9 

Number of operations for i = 5: 5 
6,6 
6,7 
6,8 
6,9 

Number of operations for i = 6: 4 
7,7 
7,8 
7,9 

Number of operations for i = 7: 3 
8,8 
8,9 

Number of operations for i = 8: 2 
9,9 

Number of operations for i = 9: 1 

Number of total operations: 55