Help Big O 이해하기

Question

Big O 및 Theta 이론을 빨리 이해할 수있는 좋은 설명을 찾으려고합니다. 저는 항상 수백 가지의 다른 방법으로 설명을 할 수 있다고 생각합니다. 그리고 나는 그 설명이 마침내 의미가 있다고 생각합니다. 나는 이것이 n00b 문제라는 것을 알고 있지만 어떤 도움을 주시면 감사하겠습니다.

Answer 1

StackOverflow 사람들은 내 telephone book example을 걷어차는 것처럼 보입니다. Big O For Eight Year Olds을 (를) 좋아할 수도 있습니다.

Answer 2

혼란의 한 가지 이유는 O (2n), 목록의 각 항목에 대해 두 가지 작업을 수행하는 것, 그리고 O (n)이라고 생각할 수있는 다른 것이 실제로 모두 O로 간주되는 이유입니다 (n)

거대한 데이터 세트 작업을 시작할 때 O (2n)과 O (n)의 차이점은 O (n)과 비교할 때 실제로 큰 차이가 아닙니다.^2) 또는 O (log N). 데이터 집합을 검색하는 3 가지 검색 알고리즘이 있다면 고려하십시오. 데이터 세트에는 백만 개의 항목이 포함되어 있습니다. 연산의 수는 각각의 알고리즘이 걸릴 것이다 :

O (2N)을 = 2,000,000

O (N) = 1,000,000

O (N^2) = 1,000000000000

오 (2N) O (n)의 2 배에 불과하지만 O (n^2)는 백만 배나 느립니다. 그것은 엄청나게 큰 차이입니다! Big O 표기법은 실제로 알고리즘이 "비례하는"방법 즉, 더 크고 더 큰 데이터 세트를 고려할 때 알고리즘이 얼마나 잘 수행되는지를 다루고 있습니다.

O (n^2) 알고리즘은 매우 작은 데이터 세트에서는 성능이 좋지만 데이터 세트가 많을수록 성능이 크게 떨어집니다. O (2n) 및 O (n)은 고르게 점진적으로 저하되며, 이는 더 많은 데이터로 작업하는 사용자가 기대하는 것과 유사합니다.

사람들이 O (2n)에 대해 말하지 않고, 둘 다 선형 시간을 나타낼 것이기 때문에 (O (n)에 대해 이야기합니다. 데이터를 추가 할 때 연산 수가 균등하게 점차 증가한다는 점에서 선형 임) .

느린 속도로 두 번 수행하는 다른 알고리즘이 여전히 O (n)으로 간주되지만, 큰 O 표기는 상대 속도의 척도가 아니라고 생각할 수 있습니다. Big O 표기법은 처리중인 데이터의 양과 관련하여 알고리즘의 비율을 조정하는 방법입니다.

Answer 3

Big O는 알고리즘을 비교하는 데 사용되는 분석 도구입니다. Big O는 함수의 상한입니다. 상한값은 알고리즘이 실행될 수있는 최대 시간으로 생각하십시오.

Big O는 변수 n을 사용하여 알고리즘의 다양한 요소를 나타냅니다. 예를 들어 배열의 모든 요소에 대해 연산을 수행하는 경우 n은 배열의 크기를 나타냅니다. n 번 작업을 수행해야합니다.

프로그래머는 알고리즘이 얼마나 복잡하고 (위에서 언급했듯이) 알고리즘의 확장 정도 (n이 커질수록 성능이 얼마나 좋은지 의미)에 대해 공통된 근거를 갖기 위해이 표기법을 사용합니다.

fibonnaci 시퀀스의 n 번째 요소를 계산하는 알고리즘은 Big O 표기법에서 매우 통찰력이 있습니다.(

fib(n) { 
    if (n == 0) 
    return 0; 
    else if (n == 1) 
    return 1; 
    else 
    return fib(n-1) + fib(n-2); 
} 

이 상관 없음 우리는 O 것으로이 알고리즘을 분류 (100) 말보다 더 정말 느리게 실행 시간 피보나치의 간단한 구현 2를 다음 fibonnaci 시퀀스의 n 번째 요소를 해결하기위한 재귀 적 방법을 고려^n) 그래프에서 지수 속도로 증가합니다. Exponential은 은행 계좌의 금액을 처리 할 때 훌륭하지만 알고리즘을 처리 할 때는 지독합니다.

피보나치의 다른 구현으로 알고리즘 속도를 크게 높일 수 있습니다.

fib(n) { 
    fibArr[n + 1]; 
    fibArr[0] = 0; 
    fibArr[1] = 1; 


    for(int i = 2; i <= n; i++) { 
    fibArr[i] = fibArr[i-1] + fibArr[i-2]; 
    } 
return fibArr[n]; 
} 

피보나시의 두 번째 구현은 Big O 실행 시간이 O (n)입니다. 이것은 선형 시간이라고 불리는 것입니다. Fibonnaci의 구현을 그래프에 대해 서로 대입하면 선형 구현과 비교하여 지수 구현의 실행 시간에 큰 차이가 있음을 알 수 있습니다.

Size - Linear - Exponential 
1  1   2 
10  10   1024 
100  100  1.2676506e+30 
1000  1000  1.071509e+301 

수행해야 할 작업의 양을 각각 고려하십시오. 각 작업에 1ms (추정치)가 걸리면 알고리즘이 얼마나 오래 걸릴지 추측 할 수 있습니다.

Big O 분석에는 더 많은 것이 있습니다. 이 알고리즘을 수행하는 데 필요한 대략적인 실행 시간과 공간을 이해하는 것이 중요 알고리즘을 선택할 때 큰 O.

Constant time - O(1) 
Logarithmic - O(logn) 
Linear - O(n) 
Quadratic - O(n^2) 
Exponential - O(2 ^n) 
Factorial - O(n!) 

에 대한 분류의 서로 다른 유형을 고려하십시오.