[Algorithm] 빅 오, 어떻게 계산하시오 / 대략입니까?



Answers

Big O는 알고리즘의 시간 복잡성에 대한 상한을 제공합니다. 일반적으로 데이터 세트 (목록) 처리와 함께 사용되지만 다른 곳에서 사용될 수 있습니다.

C 코드에서 어떻게 사용되는지에 대한 몇 가지 예입니다.

우리가 n 개의 원소들의 배열을 가지고 있다고 가정 해보자.

int array[n];

배열의 첫 번째 요소에 액세스하려면 O (1)이됩니다. 배열의 크기가 중요하지 않으므로 첫 번째 항목을 가져 오는 데 항상 동일한 일정 시간이 걸립니다.

x = array[0];

목록에서 번호를 찾으려면 다음을 수행하십시오.

for(int i = 0; i < n; i++){
    if(array[i] == numToFind){ return i; }
}

이 숫자는 O (n)입니다. 숫자를 찾기 위해 전체 목록을 살펴 봐야하기 때문입니다. Big-O는 알고리즘의 상한선을 기술하기 때문에 (오메가는 하한을, 세타는 단단히 묶어두기 때문에) Big-O는 여전히 O (n)입니다. .

중첩 루프가되면 :

for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
        array[j] += 2;
    }
}

이것은 외부 루프 (O (n))의 각 패스에 대해 전체 목록을 다시 거쳐야하므로 n이 n을 제곱하고 남겨 두어 곱하기 때문에 O (n ^ 2)입니다.

이것은 표면을 간신히 긁어 내지 만 좀 더 복잡한 알고리즘을 분석 할 때 교정과 관련된 복잡한 수학이 작용합니다. 희망이 당신이 최소한 기본에 익숙해.

Question

CS 학위를 가진 대부분의 사람들은 Big O가 무엇을 의미 하는지 확실히 알게 될 것 입니다 . 알고리즘이 실제로 얼마나 효율적인지를 측정하는 데 도움이됩니다 . 문제를 해결하려고하는 문제어떤 범주있는지 알면 그 여분의 작은 성능을 여전히 압축 할 수 있는지 파악할 수 있습니다. 1

그러나 궁금한 점은 알고리즘의 복잡성을 어떻게 계산하거나 대략적으로 계산합니까?

1 그러나 그들이 말했듯이, 그것을 과용하지 말아야한다. 조숙 한 최적화는 모든 악의 근원이며 , 정당화 된 원인이없는 최적화는 그 이름을 받아야한다.




For code A, the outer loop will execute for n+1 times, the '1' time means the process which checks the whether i still meets the requirement. And inner loop runs n times, n-2 times.... Thus, 0+2+..+(n-2)+n= (0+n)(n+1)/2= O(n²).

For code B, though inner loop wouldn't step in and execute the foo(), the inner loop will be executed for n times depend on outer loop execution time, which is O(n)




작은 알림 : big O 표기법은 점근 적 복잡성 (즉, 문제의 크기가 무한대로 커질 때)을 나타 내기 위해 사용되며 상수를 숨 깁니다.

이것은 O (n)의 알고리즘과 O (n 2 )의 알고리즘 사이에서 가장 빠른 것이 항상 첫 번째 알고리즘이 아니라는 것을 의미합니다 (크기> n의 문제에 대해 항상 첫 번째 알고리즘이 가장 빠른).

숨겨진 상수는 구현에 따라 다릅니다.

또한 경우에 따라 런타임은 입력 크기 n의 결정적 함수가 아닙니다. 예를 들어 빠른 정렬을 사용하여 정렬을 수행합니다. n 개의 요소 배열을 정렬하는 데 필요한 시간은 상수가 아니지만 배열의 시작 구성에 따라 달라집니다.

다양한 시간 복잡성이 있습니다.

  • 최악의 경우 (일반적으로 알아 내기가 쉽지만 항상 의미있는 것은 아닙니다)
  • 평균 사례 (보통 알아내는 것이 훨씬 더 힘듭니다 ...)

  • ...

좋은 소개는 R. Sedgewick과 P. Flajolet 의 알고리즘 분석 소개 입니다.

말하듯이, premature optimisation is the root of all evil 이며 (가능한 경우) 코드를 최적화 할 때 항상 프로파일 링을 사용해야합니다. 알고리즘의 복잡성을 결정하는 데 도움이 될 수도 있습니다.




당신의 비용이 다항식이라면 승수없이 최상위 항을 유지하십시오. 예 :

O (n2 / 4) = O (n2) = O (n2 / 4 + n / 2) = O

이것은 무한 시리즈에서 작동하지 않습니다. 일반적인 경우에 대한 단일 제조법은 없지만 다음과 같은 부등식이 적용됩니다.

O ( N ) <O ( N ) <O ( N ) <O ( N )




메모리 자원이 제한되어있는 경우 우려의 원인이 될 수있는 공간 복잡성도 허용하는 것을 잊지 마십시오. 예를 들어 알고리즘을 사용하는 공간의 양이 코드 내부의 어떤 요소에도 의존하지 않는다는 것을 기본적으로 말하는 방식 인 일정 공간 알고리즘을 원하는 사람이있을 수 있습니다.

때때로 복잡성은 호출되는 횟수, 루프 실행 빈도, 메모리 할당 빈도 등으로이 질문에 답하는 또 다른 부분입니다.

마지막으로 big O는 알고리즘이 얼마나 나쁜지를 설명하는 데 사용되는 최악의 경우 인 최악의 경우, 최상의 경우 및 할부 상화의 경우에 사용할 수 있습니다.




Big O 표기법은 작업하기 쉽고 불필요한 정의에 대한 불필요한 복잡성과 세부 정보를 숨기므로 유용합니다. 분단 및 정복 알고리즘의 복잡성을 해결하는 좋은 방법 중 하나는 트리 방식입니다. 메디 언 프로 시저가있는 quicksort 버전을 가지고 있다고 가정 해 봅시다. 매번 완벽하게 균형 잡힌 서브 어레이로 배열을 분할합니다.

이제 작업하는 모든 배열에 해당하는 트리를 작성하십시오. 루트에 원래 배열이 있고 루트에는 하위 배열 인 두 개의 자식이 있습니다. 아래쪽에 단일 요소 배열이 생길 때까지이 단계를 반복하십시오.

O (n) 시간에 중앙값을 찾고 O (n) 시간에 두 부분으로 배열을 나눌 수 있으므로 각 노드에서 수행 된 작업은 O (k)입니다. 여기서 k는 배열의 크기입니다. 트리의 각 레벨에는 (최대로) 전체 배열이 포함되어 있으므로 레벨 당 작업량은 O (n)입니다 (서브 어레이의 크기가 n까지 합쳐지며 레벨 당 O (k)가 있으므로이를 추가 할 수 있습니다) . 우리가 입력을 반으로 줄일 때마다 트리에는 log (n) 레벨 만 존재합니다.

따라서 우리는 작업량을 O (n * log (n))로 상한 할 수 있습니다.

그러나 Big O는 간혹 무시할 수없는 세부 사항을 숨 깁니다. 피보나치 수열을 다음과 같이 계산하는 것을 고려하십시오.

a=0;
b=1;
for (i = 0; i <n; i++) {
    tmp = b;
    b = a + b;
    a = tmp;
}

a와 b가 Java의 BigInteger이거나 임의로 큰 숫자를 처리 할 수있는 것으로 가정합니다. 대부분의 사람들은 이것이 flinching하지 않고 O (n) 알고리즘이라고 말할 것입니다. 추론은 for 루프에 n 개의 반복이 있고 루프 (loop)에서 O (1)이 작동한다는 것입니다.

그러나 피보나치 수가 크면 n 번째 피보나치 수는 n에서 지수 함수가됩니다. 따라서 저장하는 데 n 바이트가 걸릴 것입니다. 큰 정수로 덧셈을 수행하면 O (n) 개의 작업량이 필요합니다. 따라서이 절차에서 수행 된 총 작업량은

1 + 2 + 3 + ... + n = n (n-1) / 2 = O (n ^ 2)

그래서이 알고리즘은 quadradic 시간에 실행됩니다!




기본적으로 시간의 90 %까지 자르는 것은 단지 루프를 분석하는 것입니다. 싱글, 더블, 트리플 중첩 루프가 있습니까? O (n), O (n ^ 2), O (n ^ 3) 실행 시간이 있습니다.

아주 드물게 (예를 들어, .NET BCL이나 C ++의 STL과 같은) 광범위한 기반 라이브러리를 사용하지 않는 한 루프를 보는 것보다 더 어려운 것이 있습니다 (statement, while, goto, 기타...)




시작부터 시작하자.

우선 O(1) 시간, 즉 입력 크기와 무관 한 시간에 데이터에 대한 간단한 조작을 수행 할 수 있다는 원칙을 수용합니다. C의 이러한 원시 연산은

  1. 산술 연산 (예 : + 또는 %).
  2. 논리 연산 (예 : &&).
  3. 비교 연산 (예 : <=).
  4. 구조체 액세스 연산 (예 : A [i]와 같은 배열 인덱싱 또는 -> 연산자로 이어지는 포인터).
  5. 값을 변수에 복사하는 것과 같은 간단한 할당.
  6. 라이브러리 함수를 호출합니다 (예 : scanf, printf).

이 원칙에 대한 정당성은 일반적인 컴퓨터의 기계 명령 (기본 단계)에 대한 자세한 연구가 필요합니다. 설명 된 각 작업은 몇 가지 적은 수의 기계 명령어로 수행 할 수 있습니다. 종종 하나 또는 두 개의 명령 만 필요합니다. 결과적으로, C에서 몇 가지 종류의 명령문은 O(1) 시간, 즉 입력에 독립적 인 일정한 시간 동안 실행될 수 있습니다. 이 간단한 포함

  1. 표현식에 함수 호출을 포함하지 않는 할당 문.
  2. 문장을 읽습니다.
  3. 인수를 평가하기 위해 함수 호출이 필요하지 않은 명령문을 작성하십시오.
  4. jump 문은 break, continue, goto 및 return expression을 포함하며 expression에는 함수 호출이 포함되지 않습니다.

C에서 많은 for-loops는 인덱스 변수를 어떤 값으로 초기화하고 루프를 돌 때마다 그 변수를 1 씩 증가시킴으로써 형성됩니다. for-loop는 인덱스가 어느 정도 한계에 도달하면 종료됩니다. 예를 들어, for-loop

for (i = 0; i < n-1; i++) 
{
    small = i;
    for (j = i+1; j < n; j++)
        if (A[j] < A[small])
            small = j;
    temp = A[small];
    A[small] = A[i];
    A[i] = temp;
}

인덱스 변수 i를 사용합니다. 루프를 돌 때마다 i를 1 씩 증가시키고, 반복이 n - 1에 도달하면 반복을 중지합니다.

그러나 for-loop의 간단한 형태에 초점을 맞추고 있습니다. 여기서는 최종 값과 초기 값차이를 인덱스 변수가 증가하는 양으로 나눈 값이 루프를 몇 번 반복하는지 알려줍니다 . 점프 문을 통해 루프를 빠져 나갈 수있는 방법이 없으면 그 수는 정확합니다. 어떤 경우에도 iteration의 상한선이다.

예를 들어, for 루프는 i가 i의 초기 값이기 때문에 ((n − 1) − 0)/1 = n − 1 times 하고, n - 1은 i가 도달 한 최대 값입니다 (즉, n-1이면 루프가 중지되고 i = n-1로 반복이 발생하지 않음) 루프의 각 반복에서 1이 i에 추가됩니다.

가장 간단한 경우, 루프 본문에서 소비 된 시간이 각 반복마다 동일 할 경우 본문의 큰 상한선에 루프 주위의 횟수를 곱할 수 있습니다 . 엄밀히 말해 루프 인덱스를 초기화하기 위해 O (1) 시간을, 루프 인덱스를 처음으로 비교하기 위해 O (1) 시간을 추가 해야합니다. 왜냐하면 루프를 돌아 다니는 것보다 한 번 더 테스트하기 때문입니다. 그러나 루프를 0 번 실행할 수 없으면 루프를 초기화하고 한 번만 테스트하는 시간은 합계 규칙에 의해 삭제할 수있는 하위 순서입니다.

이제이 예제를 살펴보십시오.

(1) for (j = 0; j < n; j++)
(2)   A[i][j] = 0;

우리는 선 (1)O(1) 시간이 걸린다는 것을 압니다. 우리는 line (1)에서 발견 된 상한선에서 하한선을 뺀 다음 1을 더하는 것으로 결정할 수 있으므로 분명히 루프를 n 번 돌았습니다. body (2) 본문은 O (1) 시간이 걸리므로, 우리는 j를 늘릴 시간과 n과 j를 비교할 시간을 무시할 수 있습니다. 둘 다 O (1)입니다. 따라서, 선 (1)과 선 (2)의 실행 시간은 n과 O (1)곱이며 , O(n) 이다.

유사하게, (2)에서 (4)까지의 라인으로 구성된 외부 루프의 실행 시간을 제한 할 수 있습니다.

(2) for (i = 0; i < n; i++)
(3)     for (j = 0; j < n; j++)
(4)         A[i][j] = 0;

우리는 이미 회선 (3)과 (4)의 루프가 O (n) 시간이 걸린다는 것을 확증했다. 따라서 우리는 i를 증가시키고 각 반복에서 i <n인지 테스트하기 위해 O (1) 시간을 무시할 수 있습니다. 외부 루프의 각 반복이 O (n) 시간이 걸린다는 결론을 내릴 수 있습니다.

외부 루프의 초기화 i = 0과 조건 i <n의 (n + 1) 번째 테스트는 마찬가지로 O (1) 시간이 걸리고 무시 될 수 있습니다. 마지막으로 우리는 외부 반복을 n 번 반복하며, 각 반복마다 O (n) 시간을 가져서 총 O(n^2) 실행 시간을 제공한다는 것을 관찰합니다.

보다 실제적인 예.




일반적으로 덜 유용하다고 생각합니다. 그러나 알고리즘의 복잡성에 대한 하한을 정의하는 Big Omega Ω 과 상한과 하한을 정의하는 Big Theta Θ가 있습니다.




great question!

If you're using the Big O, you're talking about the worse case (more on what that means later). Additionally, there is capital theta for average case and a big omega for best case.

Check out this site for a lovely formal definition of Big O: https://xlinux.nist.gov/dads/HTML/bigOnotation.html

f(n) = O(g(n)) means there are positive constants c and k, such that 0 ≤ f(n) ≤ cg(n) for all n ≥ k. The values of c and k must be fixed for the function f and must not depend on n.

Ok, so now what do we mean by "best-case" and "worst-case" complexities?

This is probably most clearly illustrated through examples. For example if we are using linear search to find a number in a sorted array then the worst case is when we decide to search for the last element of the array as this would take as many steps as there are items in the array. The best case would be when we search for the first element since we would be done after the first check.

The point of all these adjective -case complexities is that we're looking for a way to graph the amount of time a hypothetical program runs to completion in terms of the size of particular variables. However for many algorithms you can argue that there is not a single time for a particular size of input. Notice that this contradicts with the fundamental requirement of a function, any input should have no more than one output. So we come up with multiple functions to describe an algorithm's complexity. Now, even though searching an array of size n may take varying amounts of time depending on what you're looking for in the array and depending proportionally to n, we can create an informative description of the algorithm using best-case, average-case, and worst-case classes.

Sorry this is so poorly written and lacks much technical information. But hopefully it'll make time complexity classes easier to think about. Once you become comfortable with these it becomes a simple matter of parsing through your program and looking for things like for-loops that depend on array sizes and reasoning based on your data structures what kind of input would result in trivial cases and what input would result in worst-cases.




첫 번째 경우에는 내부 루프가 ni 번 실행되므로 총 실행 횟수는 ni 0 보다 작거나 같기 때문에 총 실행 횟수는 0 부터 n-1 까지의 합계입니다. 마지막으로 n*(n + 1) / 2 가되므로 O(n²/2) = O(n²) 됩니다.

두 번째 루프의 경우 i 는 외부 루프에 대해 0n 사이에 포함됩니다. jn 보다 엄격하게 큰 경우에는 내부 루프가 실행되므로 불가능합니다.




Links