algorithm - 증명 - 알고리즘 시간 복잡도 개념




알고리즘의 시간 복잡성을 찾는 방법 (6)

질문

알고리즘의 시간 복잡성을 찾는 방법?

나에 대한 질문을 게시하기 전에 내가 뭘 했니?

나는 this 과 많은 다른 연결을 통해 갔다.

그러나 시간 복잡성을 계산하는 방법에 대한 명확하고 솔직한 설명을 어디서 찾을 수 있었는지는 알 수 없습니다.

내가 뭘 알 겠어 ?

아래 코드와 같이 간단하게 코드를 작성하십시오.

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

아래에있는 것과 같은 루프를 말하십시오 :

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; 이것은 한 번만 실행됩니다. 시간은 실제로 i=0 계산되고 선언은 계산되지 않습니다.

i <N; 이것은 N + 1 번 실행됩니다.

나는 ++; 이것은 N 번 실행됩니다.

따라서이 루프에 필요한 작업의 수는

{1+ (N + 1) + N} = 2N + 2

참고 : 시간 복잡성 계산에 대한 자신감이 나쁘기 때문에 여전히 잘못된 것일 수 있습니다.

내가 뭘 알고 싶니?

좋습니다. 그래서이 작은 기본 계산은 제가 아는 것 같지만, 대부분의 경우 시간 복잡성을 다음과 같이 보았습니다.

O (N), O (n2), O (log n), O (n!

누구나 알고리즘의 시간 복잡도를 계산하는 방법을 이해할 수 있습니까? 나는 이것을 알고 싶어하는 많은 초보자가있을 것이라고 확신한다.


알고리즘의 시간 복잡성을 찾는 방법

실행될 머신 명령어의 수를 입력 크기의 함수로 더한 다음 가장 큰 표현식 (N이 매우 큰 경우)을 단순화하고 단순화 상수 요소를 포함 할 수 있습니다.

예를 들어, 2N + 2 기계 명령어를 단순화하여 O(N) 2N + 2 설명 할 수 있습니다.

왜 우리는 2 개의 2 제거합니까?

우리는 N이 커질수록 알고리즘의 성능에 관심이 있습니다.

2N과 2의 두 용어를 고려하십시오.

N이 커질수록이 두 용어의 상대적인 영향은 무엇입니까? N이 백만이라고 가정합니다.

그러면 첫 번째 학기는 2 백만이고 두 번째 학기는 2입니다.

이러한 이유 때문에 우리는 큰 N에 대한 가장 큰 용어를 제외한 모든 것을 버립니다.

이제 우리는 2N + 2 에서 2N + 2 갔습니다.

전통적으로 우리는 일정한 요소까지만 성능에 관심이 있습니다.

이것은 N이 클 때 성능에 일정한 배수 차이가 있는지에 대해 실제로 신경 쓰지 않는다는 것을 의미합니다. 어쨌든 2N의 단위는 잘 정의되어 있지 않습니다. 그래서 우리는 가장 단순한 표현을 얻기 위해 상수를 곱하거나 나눌 수 있습니다.

그래서 2N 은 단지 N 됩니다.


예제를 사용한 시간 복잡성

1 - 기본 연산 (산술, 비교, 배열 요소 액세스, 할당) : 실행 시간은 항상 일정 O (1)

예 :

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - If then else statement : 둘 이상의 가능한 명령문에서 최대 실행 시간 만 가져옵니다.

예:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

따라서, 위의 의사 코드의 복잡성은 T (n) = 2 + 1 + max (1,1 + 2) = 6입니다. 따라서 큰 오 여전히 T (n) = O (1)입니다.

3 - 루핑 (for, while, repeat) :이 명령문의 실행 시간은 루핑 수에 루핑 내부의 연산 수를 곱한 것입니다.

예:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

따라서, T (n) = 1 + 4n + 1 = 4n + 2이므로 T (n) = O (n)입니다.

4 - 중첩 루프 (루핑 내부 루핑) : 메인 루핑 내부에 적어도 하나의 루핑이 있으므로이 명령문의 실행 시간은 O (n ^ 2) 또는 O (n ^ 3)를 사용합니다.

예:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

일반적인 러닝 타임

알고리즘을 분석 할 때 몇 가지 일반적인 실행 시간이 있습니다.

  1. O (1) - 상수 시간 상수 시간은 실행 시간이 일정하다는 것을 의미 하며 입력 크기의 영향을받지 않습니다 .

  2. O (n) - 선형 시간 알고리즘이 n 입력 크기를 허용하면 n 연산도 수행합니다.

  3. O (log n) - 실행 시간이 O (log n) 인 Logarithmic Time Algorithm은 O (n)보다 약간 빠릅니다. 일반적으로 알고리즘은 문제를 동일한 크기의 하위 문제로 나눕니다. 예 : 2 진 검색 알고리즘, 2 진 변환 알고리즘.

  4. O (n log n) - 선형 시간이 실행 ​​시간은 종종 문제를 하위 문제로 반복적으로 나눈 다음 n 시간에 병합하는 "나누기 및 정복 알고리즘"에서 찾을 수 있습니다. 예 : Merge Sort 알고리즘.

  5. O (n 2 ) - Quadratic Time Look Bubble Sort 알고리즘!

  6. O (n 3 ) - 입방체 시간 그것은 O (n 2 )와 같은 원리입니다.

  7. O (2 n ) - 지수 시간 입력이 커지면 매우 느려지고, n = 1000.000이면 T (n)은 21000.000이됩니다. Brute Force 알고리즘에는이 실행 시간이 있습니다.

  8. O (n!) - Factorial Time 가장 느림 !!! 예 : 여행 세일즈맨 문제 (TSP)

이 기사 에서 가져온 . 아주 잘 설명하면 읽을 거리가 있어야합니다.


나는이 질문이 돌아가는 길을 알고 있으며 여기에 몇 가지 훌륭한 해답이있다. 그럼에도 불구하고 나는이 포스트에서 비틀 거릴 수학적 사고를 가진 사람들에게 또 하나의 비트를 나누고 싶었다. Master theorem 은 복잡성을 연구 할 때 알아 두어야 할 또 다른 유용한 정보입니다. 나는 다른 대답에서 언급 된 것을 보지 못했습니다.


느슨하게 말하자면, 시간 복잡도는 입력 크기가 증가함에 따라 알고리즘의 연산 수 또는 실행 시간이 어떻게 증가 하는지를 요약하는 방법입니다.

삶의 대부분과 마찬가지로 칵테일 파티도 우리를 이해하는 데 도움이 될 수 있습니다.

에)

파티에 도착하면 모든 사람의 손을 흔들어야합니다 (모든 항목을 조작하십시오). 참석자 수 N 증가함에 따라, 모든 사람의 손을 흔들기 위해 걸리는 시간 / 작업이 O(N) 만큼 증가합니다.

O(N) 가 아닌 cN 입니까?

사람들과 악수하는 데 소요되는 시간에는 변동이 있습니다. 이것을 평균하여 상수 c 포착 할 수 있습니다. 그러나 근본적인 작동 --- 모든 사람들과 악수 ---는 c 가 무엇이든 항상 O(N) 비례합니다. 우리가 칵테일 파티에 가야하는지 여부를 논할 때, 우리는 종종 회의가 어떻게 생겼는지에 대한 세부 사항보다 모든 사람을 만나야한다는 사실에 더 관심이 있습니다.

O (N ^ 2)

칵테일 파티의 주인은 모두가 다른 사람들을 만나는 어리석은 게임을 원합니다. 따라서 N-1 명의 다른 사람을 만나야하며 다음 사람이 이미 당신을 만났기 때문에 N-2 명의 사람들을 만나야합니다. 이 시리즈의 합은 x^2/2+x/2 입니다. 참석자의 수가 늘어남에 따라 x^2 용어가 크게 빨라 지기 때문에 다른 모든 것을 버립니다.

O (N ^ 3)

다른 사람들을 만나야하고, 각 회의 중에 방 안의 다른 모든 사람들에 대해서 이야기해야합니다.

O (1)

주최자가 뭔가를 발표하려고합니다. 그들은 와인 잔을 부르고 큰 소리로 말한다. 모두들 그 소리를 듣는다. 얼마나 많은 참석자가 있더라도 상관 없습니다.이 작업에는 항상 동일한 시간이 걸립니다.

O (log N)

주인은 모든 사람들을 알파벳순으로 테이블에 눕혔습니다. 댄은 어디 있습니까? 당신은 그가 아담과 맨디 사이의 어딘가에 있어야한다고 생각합니다 (확실히 맨디와 잭 사이는 아닙니다!). 그걸 감안할 때, 그는 조지와 맨디 사이에 있습니까? 아담과 프레드, 신디와 프레드 사이에 있어야합니다. 그리고 우리는 댄의 세트를 반으로보고 그 반을 보면서 댄을 효율적으로 찾을 수 있습니다. 궁극적으로 우리는 O (log_2 N) 개체를 봅니다.

O (NlogN)

위의 알고리즘을 사용하여 테이블에 앉을 위치를 찾을 수 있습니다. 많은 사람들이 한 번에 하나씩 테이블에 왔을 때 모두 O (N log N) 시간이 걸릴 것입니다. 이것은 비교해야 할 항목의 컬렉션을 정렬하는 데 걸리는 시간입니다.

최고 / 최악의 경우

당신은 파티에 도착하여 이니고를 찾아야합니다 - 얼마나 걸릴까요? 도착한시기에 따라 다릅니다. 모두가 주변에서 밀링 작업을하는 경우 최악의 경우를 맞았습니다. O(N) 시간이 걸릴 것입니다. 그러나 모든 사람이 테이블에 앉아 있으면 O(log N) 시간 만 걸릴 것입니다. 또는 호스트의 와인 글라스를 외치는 힘을 활용할 수 있으며 O(1) 시간 만 소요됩니다.

호스트를 사용할 수 없다고 가정 할 때, Inigo-finding 알고리즘은 당신이 도착했을 때 당사자의 상태에 따라 O(log N) 하한과 O(N) 의 상한을 가지고 있다고 말할 수 있습니다.

우주 및 커뮤니케이션

알고리즘이 공간 또는 통신을 사용하는 방식을 이해하는 데에도 동일한 아이디어를 적용 할 수 있습니다.

크 누스 (Knuth)는 "The Complexity of Songs (노래의 복잡성)" 이라는 제목의 훌륭한 종이를 썼습니다.

정리 2 : 복잡성 O (1)의 임의의 긴 노래가 존재한다.

증명 : (Casey와 Sunshine Band 때문에). (15)에 의해 정의 된 노래 Sk를 고려해 보자.

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

모든 k.


이 질문에 대한 좋은 대답이 있지만. loop 대한 몇 가지 예를 들어 여기에 다른 답변을 드리겠습니다.

  • O (n) : 루프 변수가 일정한 양만큼 증가 / 감소되면 루프의 시간 복잡도는 O (n) 으로 간주됩니다. 예를 들어, 다음 함수는 O (n) 시간 복잡성을가집니다.

    // Here c is a positive integer constant   
    for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
    }
    
    for (int i = n; i > 0; i -= c) {
        // some O(1) expressions
    }
    
  • O (n ^ c) : 중첩 루프의 시간 복잡도는 가장 안쪽 명령문이 실행 된 횟수와 같습니다. 예를 들어, 다음 샘플 루프는 O (n ^ 2) 시간 복잡도를가집니다.

    for (int i = 1; i <=n; i += c) {
       for (int j = 1; j <=n; j += c) {
          // some O(1) expressions
       }
    }
    
    for (int i = n; i > 0; i += c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
    }
    

    예를 들어 선택 정렬 및 삽입 정렬에는 O (n ^ 2) 시간 복잡도가 있습니다.

  • O (Logn) Time 루프 변수가 일정량으로 나누거나 곱해진 경우 루프의 복잡도는 O (Logn) 로 간주됩니다.

    for (int i = 1; i <=n; i *= c) {
       // some O(1) expressions
    }
    for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
    }
    

    예를 들어, 바이너리 서치는 O (Logn) 시간 복잡성이 있습니다.

  • O (LogLogn) Time 루프 변수가 일정한 양만큼 지수 함수 적으로 감소 / 증가하면 루프의 복잡도는 O (LogLogn) 로 간주됩니다.

    // Here c is a constant greater than 1   
    for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
    }
    //Here fun is sqrt or cuberoot or any other constant root
    for (int i = n; i > 0; i = fun(i)) { 
       // some O(1) expressions
    }
    

시간 복잡도 분석의 한 예

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

분석 :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

따라서 위의 알고리즘의 총 시간 복잡도는 (n + n/2 + n/3 + … + n/n) 이며 n * (1/1 + 1/2 + 1/3 + … + 1/n)

시리즈 (1/1 + 1/2 + 1/3 + … + 1/n) 에 대한 중요한 점은 O (Logn)와 같습니다 . 따라서 위 코드의 시간 복잡도는 O (nLogn) 입니다.

참고 : 1 2 3


이것은 훌륭한 기사입니다 : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

아래의 답변은 위에서 복사 한 것입니다 (우수한 링크가 파열되는 경우를 대비하여)

시간 복잡도를 계산하는 가장 일반적인 통계는 Big O 표기법입니다. 이렇게하면 N이 N에 가까워 질수록 실행 시간이 N과 관련하여 추정 될 수 있도록 모든 상수 요소가 제거됩니다. 일반적으로 다음과 같이 생각할 수 있습니다.

statement;

상수입니다. 명령문의 실행 시간은 N과 관련하여 변경되지 않습니다.

for ( i = 0; i < N; i++ )
     statement;

선형이야. 루프의 실행 시간은 N에 정비례합니다. N이 두 배가되면 실행 시간도 늘어납니다.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

2 차입니다. 두 개의 루프의 실행 시간은 N의 제곱에 비례합니다. N이 두 배가되면 실행 시간이 N * N만큼 증가합니다.

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

대수적입니다. 알고리즘의 실행 시간은 N을 2로 나눌 수있는 횟수에 비례합니다. 알고리즘이 작업 영역을 각 반복과 반으로 나누기 때문입니다.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

N * log (N)입니다. 실행 시간은 대수적 인 N 개의 루프 (반복 또는 반복)로 구성되므로 알고리즘은 선형 및 로그의 조합입니다.

일반적으로 한 항목의 모든 항목을 선형으로 처리하는 것은 2 차원의 모든 항목에 대해 무언가를 수행하는 것이 2 차이고 작업 영역을 절반으로 나누는 것이 로그입니다. 큐빅, 지수 및 제곱근과 같은 다른 Big O 측정 값이 있지만 공통점이 거의 없습니다. Big O 표기법은 O ()로 설명됩니다. 퀵 소트 알고리즘은 O (N * log (N))로 설명됩니다.

이 중 어느 것도 최상, 평균 및 최악의 경우를 고려하지 않았습니다. 각각에는 그것의 자신의 큰 O 표기법이있을 것입니다. 또한 이것은 매우 단순한 설명입니다. 빅 오 (Big O)가 가장 보편적이지만, 내가 보여준 것이 더 복잡합니다. 큰 오메가, 작은 오, 큰 쎄타 같은 다른 표기법도 있습니다. 알고리즘 분석 과정을 거치지 않고도 이러한 문제가 발생하지 않을 것입니다. ;)





complexity-theory