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

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

---

질문

알고리즘의 시간 복잡성을 찾는 방법은 무엇입니까?

그래서 질문을 게시하기 전에 무엇을 했습니까?

나는 이것 , 이것 및 다른 많은 링크를 통과 했습니다

그러나 시간 복잡성을 계산하는 방법에 대한 명확하고 직접적인 설명을 찾을 수 없었습니다.

내가 뭘 알 겠어 ?

다음과 같이 간단한 코드를 말하십시오.

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선언이 아닌 실제로 계산됩니다 .

나는 <N; N + 1 회 실행됩니다.

i ++; N 번 실행 됩니다.

따라서이 루프에 필요한 작업 수는 다음과 같습니다.

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

참고 : 시간 복잡도 계산에 대한 이해가 확실하지 않기 때문에 여전히 잘못된 것일 수 있습니다.

내가 무엇을 알고 싶은가?

좋아,이 작은 기본 계산은 내가 알고 있다고 생각하지만 대부분의 경우 시간 복잡성을

O (N), O (n2), O (log n), O (n!) .... 및 기타 많은 ,

누구든지 알고리즘의 시간 복잡성을 계산하는 방법을 이해하도록 도울 수 있습니까? 나는 이것을 알고 싶어하는 나와 같은 많은 초보자가 있다고 확신합니다.

---

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

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

예를 들어, 2N + 2이것을 단순히 O(N).

왜 우리는 두를 제거 2합니까?

N이 커짐에 따라 알고리즘의 성능에 관심이 있습니다.

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

N이 커질 때이 두 항의 상대적 영향은 무엇입니까? N이 백만이라고 가정합니다.

그런 다음 첫 번째 기간은 2 백만이고 두 번째 기간은 2입니다.

이러한 이유로 큰 N에 대해 가장 큰 항을 제외하고 모두 삭제합니다.

그래서, 지금 우리가에서 갔다 2N + 2에 2N.

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

즉, N이 클 때 성능에 일정한 배수가 있는지 여부는 신경 쓰지 않습니다. 어쨌든 2N의 단위는 처음에 잘 정의되어 있지 않습니다. 그래서 우리는 가장 간단한 표현을 얻기 위해 상수 인자로 곱하거나 나눌 수 있습니다.

그래서 2N그냥 N됩니다.

---

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

아래 답변은 위에서 복사 한 것입니다 (우수 링크가 끊어지는 경우)

시간 복잡도를 계산하는 가장 일반적인 메트릭은 Big O 표기법입니다. 이렇게하면 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))로 설명됩니다.

이 중 어느 것도 최선, 평균 및 최악의 경우 측정 값을 고려하지 않았습니다. 각각 고유 한 Big O 표기법이 있습니다. 또한 이것은 매우 단순한 설명입니다. Big O가 가장 일반적이지만 내가 보여준 것보다 더 복잡합니다. 빅 오메가, 리틀 오, 빅 세타와 같은 다른 표기법도 있습니다. 알고리즘 분석 과정 밖에서 만나지 않을 것입니다. ;)

---

여기에서 발췌- 알고리즘의 시간 복잡성 소개

1. 소개

컴퓨터 과학에서 알고리즘의 시간 복잡성은 알고리즘이 입력을 나타내는 문자열 길이의 함수로 실행하는 데 걸리는 시간을 정량화합니다.

2. Big O 표기법

알고리즘의 시간 복잡도는 일반적으로 계수와 저차 항을 제외하는 big O 표기법을 사용하여 표현됩니다. 이렇게 표현하면 입력 크기가 무한대로 갈수록 시간 복잡도가 점근 적으로 설명된다고합니다.

예를 들어, 크기 n의 모든 입력에 대해 알고리즘에 필요한 시간이 최대 5n ³ + 3n 인 경우 점근 적 시간 복잡도는 O (n ³ )입니다. 나중에 더 자세히 설명하겠습니다.

몇 가지 더 많은 예 :

• 1 = O (n)
• n = O (n ² )
• 로그 (n) = O (n)
• 2n + 1 = O (n)

3. O (1) 일정 시간 :

알고리즘은 입력 크기에 관계없이 동일한 시간이 필요한 경우 일정한 시간에 실행된다고합니다.

예 :

• 배열 : 모든 요소에 액세스
• 고정 크기 스택 : 푸시 및 팝 메서드
• 고정 크기 대기열 : 대기열에 넣기 및 대기열에서 빼기 방법

4. O (n) 선형 시간

알고리즘은 시간 실행이 입력 크기에 정비례하는 경우 선형 시간으로 실행된다고합니다. 즉, 입력 크기가 증가함에 따라 시간이 선형 적으로 증가합니다.

다음 예제를 고려하십시오. 아래에서 요소를 선형 적으로 검색하고 있습니다. 이것은 시간 복잡성이 O (n)입니다.

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

더 많은 예 :

• 배열 : 선형 검색, 횡단, 최소 찾기 등
• ArrayList : 메소드 포함
• 큐 : 메소드 포함

5. O (log n) 로그 시간 :

알고리즘은 시간 실행이 입력 크기의 로그에 비례하는 경우 로그 시간으로 실행된다고합니다.

예 : 이진 검색

"스무 개 질문"게임을 떠올려보세요. 작업은 간격에서 숨겨진 숫자의 값을 추측하는 것입니다. 추측 할 때마다 추측이 너무 높거나 낮은 지 알려줍니다. 20 개의 질문 게임은 추측 번호를 사용하여 간격 크기를 절반으로 줄이는 전략을 의미합니다. 이진 검색으로 알려진 일반적인 문제 해결 방법의 예입니다.

6. O (n2) 2 차 시간

알고리즘은 시간 실행이 입력 크기의 제곱에 비례하는 경우 2 차 시간으로 실행된다고합니다.

예 :

• 버블 정렬
• 선택 정렬
• 삽입 정렬

7. 유용한 링크

• Big-O 오해
• 알고리즘의 복잡성 결정
• 빅 오 치트 시트

---

이 질문에 대한 좋은 답변이 있지만. 몇 가지 예를 들어 여기에 또 다른 대답을 드리고 싶습니다 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) 루프의 시간 복잡도 는 루프 변수를 일정한 양으로 나누거나 곱하면 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 Complexity of a loop is considered as O(LogLogn) if the loop variables is reduced / increased exponentially by a constant amount.

  // 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
  }
  

---

One example of time complexity analysis

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

Analysis:

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.

So the total time complexity of the above algorithm is (n + n/2 + n/3 + … + n/n), Which becomes n * (1/1 + 1/2 + 1/3 + … + 1/n)

The important thing about series (1/1 + 1/2 + 1/3 + … + 1/n) is equal to O(Logn). So the time complexity of the above code is O(nLogn).

---

Ref: 1 2 3

---

Time complexity with examples

1 - Basic Operations (arithmetic, comparisons, accessing array’s elements, assignment) : The running time is always constant O(1)

Example :

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

2 - If then else statement: Only taking the maximum running time from two or more possible statements.

Example:

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;

So, the complexity of the above pseudo code is T(n) = 2 + 1 + max(1, 1+2) = 6. Thus, its big oh is still constant T(n) = O(1).

3 - Looping (for, while, repeat): Running time for this statement is the number of looping multiplied by the number of operations inside that looping.

Example:

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

So, its complexity is T(n) = 1+4n+1 = 4n + 2. Thus, T(n) = O(n).

4 - Nested Loop (looping inside looping): Since there is at least one looping inside the main looping, running time of this statement used O(n^2) or O(n^3).

Example:

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;

Common Running Time

There are some common running times when analyzing an algorithm:

1. O(1) – Constant Time Constant time means the running time is constant, it’s not affected by the input size.

2. O(n) – Linear Time When an algorithm accepts n input size, it would perform n operations as well.

3. O(log n) – Logarithmic Time Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm.

4. O(n log n) – Linearithmic Time This running time is often found in "divide & conquer algorithms" which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm.

5. O(n²) – Quadratic Time Look Bubble Sort algorithm!

6. O(n³) – Cubic Time It has the same principle with O(n²).

7. O(2ⁿ) – Exponential Time It is very slow as input get larger, if n = 1000.000, T(n) would be 21000.000. Brute Force algorithm has this running time.

8. O(n!) – Factorial Time THE SLOWEST !!! Example : Travel Salesman Problem (TSP)

Taken from this article. Very well explained should give a read.

---

When you're analyzing code, you have to analyse it line by line, counting every operation/recognizing time complexity, in the end, you have to sum it to get whole picture.

For example, you can have one simple loop with linear complexity, but later in that same program you can have a triple loop that has cubic complexity, so your program will have cubic complexity. Function order of growth comes into play right here.

Let's look at what are possibilities for time complexity of an algorithm, you can see order of growth I mentioned above:

• Constant time has an order of growth 1, for example: a = b + c.

• Logarithmic time has an order of growth LogN, it usually occurs when you're dividing something in half (binary search, trees, even loops), or multiplying something in same way.

• Linear, order of growth is N, for example

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Linearithmic, order of growth is n*logN, usually occurs in divide and conquer algorithms.

• Cubic, order of growth N^3, classic example is a triple loop where you check all triplets:

  int x = 0;
  for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            x = x + 2
  

• Exponential, order of growth 2^N, usually occurs when you do exhaustive search, for example check subsets of some set.

---

Loosely speaking, time complexity is a way of summarising how the number of operations or run-time of an algorithm grows as the input size increases.

Like most things in life, a cocktail party can help us understand.

O(N)

When you arrive at the party, you have to shake everyone's hand (do an operation on every item). As the number of attendees N increases, the time/work it will take you to shake everyone's hand increases as O(N).

Why O(N) and not cN?

There's variation in the amount of time it takes to shake hands with people. You could average this out and capture it in a constant c. But the fundamental operation here --- shaking hands with everyone --- would always be proportional to O(N), no matter what c was. When debating whether we should go to a cocktail party, we're often more interested in the fact that we'll have to meet everyone than in the minute details of what those meetings look like.

O(N^2)

The host of the cocktail party wants you to play a silly game where everyone meets everyone else. Therefore, you must meet N-1 other people and, because the next person has already met you, they must meet N-2 people, and so on. The sum of this series is x^2/2+x/2. As the number of attendees grows, the x^2 term gets big fast, so we just drop everything else.

O(N^3)

You have to meet everyone else and, during each meeting, you must talk about everyone else in the room.

O(1)

The host wants to announce something. They ding a wineglass and speak loudly. Everyone hears them. It turns out it doesn't matter how many attendees there are, this operation always takes the same amount of time.

O(log N)

The host has laid everyone out at the table in alphabetical order. Where is Dan? You reason that he must be somewhere between Adam and Mandy (certainly not between Mandy and Zach!). Given that, is he between George and Mandy? No. He must be between Adam and Fred, and between Cindy and Fred. And so on... we can efficiently locate Dan by looking at half the set and then half of that set. Ultimately, we look at O(log_2 N) individuals.

O(N log N)

You could find where to sit down at the table using the algorithm above. If a large number of people came to the table, one at a time, and all did this, that would take O(N log N) time. This turns out to be how long it takes to sort any collection of items when they must be compared.

Best/Worst Case

You arrive at the party and need to find Inigo - how long will it take? It depends on when you arrive. If everyone is milling around you've hit the worst-case: it will take O(N) time. However, if everyone is sitting down at the table, it will take only O(log N) time. Or maybe you can leverage the host's wineglass-shouting power and it will take only O(1) time.

Assuming the host is unavailable, we can say that the Inigo-finding algorithm has a lower-bound of O(log N) and an upper-bound of O(N), depending on the state of the party when you arrive.

Space & Communication

The same ideas can be applied to understanding how algorithms use space or communication.

Knuth has written a nice paper about the former entitled "The Complexity of Songs".

Theorem 2: There exist arbitrarily long songs of complexity O(1).

PROOF: (due to Casey and the Sunshine Band). Consider the songs Sk defined by (15), but with

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

for all k.

---

I know this question goes a way back and there are some excellent answers here, nonetheless I wanted to share another bit for the mathematically-minded people that will stumble in this post. The Master theorem is another usefull thing to know when studying complexity. I didn't see it mentioned in the other answers.

---

O(n) is big O notation used for writing time complexity of an algorithm. When you add up the number of executions in an algoritm you'll get an expression in result like 2N+2, in this expression N is the dominating term(the term having largest effect on expression if its value increases or decreases). Now O(N) is the time comlexity while N is dominating term. Example

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

here total number of executions for inner loop are n+1 and total number of executions for outer loop are n(n+1)/2, so total number of executions for whole algorithm are n+1+n(n+1/2) = (n^2+3n)/2. here n^2 is the dominating term so the time complexity for this algorithm is O(n^2)

참고URL : https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm