“Big O”표기법에 대한 일반적인 영어 설명

질문 : “Big O”표기법에 대한 일반적인 영어 설명은 무엇입니까?

---

가능한 한 적은 형식적인 정의와 간단한 수학을 선호합니다.

답변

---

참고로, 이것은 Big O 표기법 (상한)과 Theta 표기법 "Θ"(양면 경계)를 거의 확실히 혼동합니다. 제 경험상, 이것은 실제로 비 학문적 인 환경에서의 일반적인 토론입니다. 혼란을 드려 죄송합니다.

Big O 복잡성은 다음 그래프로 시각화 할 수 있습니다.

Big-O 표기법에 대해 줄 수있는 가장 간단한 정의는 다음과 같습니다.

Big-O 표기법은 알고리즘의 복잡성을 상대적으로 표현한 것입니다.

그 문장에는 몇 가지 중요하고 의도적으로 선택된 단어가 있습니다.

• 상대 : 사과와 사과 만 비교할 수 있습니다. 산술 곱셈을 수행하는 알고리즘을 정수 목록을 정렬하는 알고리즘과 비교할 수 없습니다. 그러나 산술 연산 (하나의 곱셈, 하나의 덧셈)을 수행하기 위해 두 알고리즘을 비교하면 의미있는 것을 알 수 있습니다.
• 표현 : Big-O (가장 단순한 형태)는 알고리즘 간의 비교를 단일 변수로 줄입니다. 해당 변수는 관찰 또는 가정을 기반으로 선택됩니다. 예를 들어 정렬 알고리즘은 일반적으로 비교 작업 (상대적 순서를 결정하기 위해 두 노드 비교)을 기반으로 비교됩니다. 이것은 비교가 비싸다고 가정합니다. 그러나 비교가 저렴하지만 스와핑이 비싸다면 어떨까요? 비교를 변경합니다. 과
• 복잡성 : 10,000 개의 요소를 정렬하는 데 1 초가 걸리면 100 만 개의 요소를 정렬하는 데 얼마나 걸립니까? 이 경우 복잡성은 다른 것에 대한 상대적인 척도입니다.

• 상대 : 사과와 사과 만 비교할 수 있습니다. 산술 곱셈을 수행하는 알고리즘을 정수 목록을 정렬하는 알고리즘과 비교할 수 없습니다. 그러나 산술 연산 (하나의 곱셈, 하나의 덧셈)을 수행하기 위해 두 알고리즘을 비교하면 의미있는 것을 알 수 있습니다.
• 표현 : Big-O (가장 단순한 형태)는 알고리즘 간의 비교를 단일 변수로 줄입니다. 해당 변수는 관찰 또는 가정을 기반으로 선택됩니다. 예를 들어 정렬 알고리즘은 일반적으로 비교 작업 (상대적 순서를 결정하기 위해 두 노드 비교)을 기반으로 비교됩니다. 이것은 비교가 비싸다고 가정합니다. 그러나 비교가 저렴하지만 스와핑이 비싸다면 어떨까요? 비교를 변경합니다. 과
• 복잡성 : 10,000 개의 요소를 정렬하는 데 1 초가 걸리면 100 만 개의 요소를 정렬하는 데 얼마나 걸립니까? 이 경우 복잡성은 다른 것에 대한 상대적인 척도입니다.

나머지를 읽은 후 돌아와서 위의 내용을 다시 읽으십시오.

내가 생각할 수있는 Big-O의 가장 좋은 예는 산술을하는 것입니다. 두 개의 숫자 (123456 및 789012)를 가져옵니다. 학교에서 배운 기본적인 산술 연산은 다음과 같습니다.

• 부가;
• 빼기;
• 곱셈; 과
• 분할.

• 부가;
• 빼기;
• 곱셈; 과
• 분할.

이들 각각은 작업 또는 문제입니다. 이를 해결하는 방법을 알고리즘 이라고합니다.

추가는 가장 간단합니다. 숫자를 정렬하고 (오른쪽) 열에 숫자를 추가하여 결과에 해당 추가의 마지막 숫자를 기록합니다. 그 숫자의 '십'부분은 다음 열로 넘어갑니다.

이 숫자를 더하는 것이이 알고리즘에서 가장 비용이 많이 드는 작업이라고 가정 해 보겠습니다. 이 두 숫자를 더하려면 6 자리 숫자를 더해야합니다. 두 개의 100 자리 숫자를 더하면 100 개를 더해야합니다. 10,000 자리 숫자 두 개를 더하면 10,000 개를 더해야합니다.

패턴이 보이십니까? 복잡도 (작업 수)는 더 큰 숫자 의 자릿수 n에 정비례합니다. 이것을 O (n) 또는 선형 복잡도 라고 부릅니다.

뺄셈도 비슷합니다 (휴대하는 대신 빌려야 할 수도 있음을 제외하고).

곱셈은 다릅니다. 숫자를 정렬하고 맨 아래 숫자의 첫 번째 숫자를 가져 와서 위쪽 숫자의 각 숫자에 대해 차례로 곱하는 식으로 각 숫자를 통해 반복합니다. 따라서 두 개의 6 자리 숫자를 곱하려면 36 개의 곱셈을해야합니다. 최종 결과를 얻기 위해 10 개 또는 11 개의 열을 추가해야 할 수도 있습니다.

두 개의 100 자리 숫자가있는 경우 10,000 번의 곱셈과 200 개의 더하기를 수행해야합니다. 2 백만 자리 숫자에 대해 1 조 (10 ¹² ) 곱셈과 2 백만 더하기를 수행해야합니다.

알고리즘이 n- squared로 확장됨에 따라 이것은 O (n ² ) 또는 2 차 복잡도 입니다. 이것은 또 다른 중요한 개념을 소개하기에 좋은 시간입니다.

우리는 복잡성의 가장 중요한 부분에만 관심이 있습니다.

^{현명한 사람은 연산 수를 n 2} + 2n으로 표현할 수 있다는 것을 깨달았을 것입니다. 그러나 두 개의 숫자가 각각 백만 자릿수 인 우리의 예에서 보았 듯이 두 번째 항 (2n)은 중요하지 않게됩니다 (해당 단계에서 총 연산의 0.0002 %를 차지함).

여기에서 최악의 시나리오를 가정했음을 알 수 있습니다. 6 자리 숫자를 곱하는 동안 그중 하나에 4 자리 숫자가 있고 다른 하나에 6 자리 숫자가 있으면 24 개의 곱셈 만 있습니다. 그래도 'n'에 대한 최악의 시나리오, 즉 둘 다 6 자리 숫자 인 경우를 계산합니다. 따라서 Big-O 표기법은 알고리즘의 최악의 시나리오에 관한 것입니다.

다음으로 생각할 수있는 가장 좋은 예는 일반적으로 White Pages 또는 이와 유사한 전화 번호부이지만 국가마다 다릅니다. 그러나 나는 성, 이니셜 또는 이름, 아마도 주소와 전화 번호로 사람들을 나열하는 것에 대해 이야기하고 있습니다.

이제 컴퓨터에 1,000,000 개의 이름이 포함 된 전화 번호부에서 "John Smith"의 전화 번호를 찾도록 지시한다면 어떻게 하시겠습니까? S가 얼마나 시작되었는지 추측 할 수 있다는 사실을 무시하고 (할 수 없다고 가정합시다), 어떻게 하시겠습니까?

일반적인 구현은 중간까지 열고 500,000 ^번째를 취하여 "Smith"와 비교하는 것입니다. "Smith, John"이된다면 정말 운이 좋았습니다. "John Smith"가 그 이름 앞뒤에있을 가능성이 훨씬 더 높습니다. 이후라면 전화 번호부의 마지막 절반을 반으로 나누고 반복합니다. 이전이라면 전화 번호부의 전반부를 반으로 나누고 반복합니다. 등등.

이를 이진 검색 이라고하며 인식 여부에 관계없이 프로그래밍에서 매일 사용됩니다.

따라서 백만 개의 이름으로 된 전화 번호부에서 이름을 찾으려면 실제로 최대 20 번이 작업을 수행하여 모든 이름을 찾을 수 있습니다. 검색 알고리즘을 비교할 때이 비교가 'n'이라고 결정합니다.

• 이름이 3 개인 전화 번호부의 경우 최대 2 번의 비교가 필요합니다.
• 7의 경우 최대 3이 걸립니다.
• 15 인 경우 4가 걸립니다.
• …
• 1,000,000에는 20이 걸립니다.

• 이름이 3 개인 전화 번호부의 경우 최대 2 번의 비교가 필요합니다.
• 7의 경우 최대 3이 걸립니다.
• 15 인 경우 4가 걸립니다.
• …
• 1,000,000에는 20이 걸립니다.

엄청나게 좋죠?

Big-O 용어로 이것은 O (log n) 또는 로그 복잡도 입니다. 이제 문제의 로그는 ln (밑 e), log ₁₀ , log ₂ 또는 다른 밑이 될 수 있습니다. ^{O (2n 2} ) 및 O (100n ² )가 여전히 O (n ² ) 인 것처럼 여전히 O (log n) 인 것은 중요하지 않습니다.

이 시점에서 Big O를 사용하여 알고리즘으로 세 가지 경우를 결정할 수 있음을 설명하는 것이 좋습니다.

• 최상의 경우 : 전화 번호부 검색에서 가장 좋은 경우는 하나의 비교에서 이름을 찾는 것입니다. 이것은 O (1) 또는 일정한 복잡성입니다 .
• 예상되는 경우 : 위에서 논의한 바와 같이 이것은 O (log n); 과
• 최악의 경우 : 이것은 또한 O (log n)입니다.

• 최상의 경우 : 전화 번호부 검색에서 가장 좋은 경우는 하나의 비교에서 이름을 찾는 것입니다. 이것은 O (1) 또는 일정한 복잡성입니다 .
• 예상되는 경우 : 위에서 논의한 바와 같이 이것은 O (log n); 과
• 최악의 경우 : 이것은 또한 O (log n)입니다.

일반적으로 우리는 최상의 경우에 대해 신경 쓰지 않습니다. 우리는 예상되는 최악의 경우에 관심이 있습니다. 때때로 이들 중 하나 또는 다른 것이 더 중요 할 것입니다.

전화 번호부로 돌아갑니다.

전화 번호가 있고 이름을 찾으려면 어떻게합니까? 경찰은 역 전화 번호부를 가지고 있지만 이러한 조회는 일반 대중에게 거부됩니다. 아니면 그들은? 기술적으로는 일반 전화 번호부에서 번호를 역 조회 할 수 있습니다. 어떻게?

이름부터 시작하여 숫자를 비교합니다. 일치하면 훌륭하지만 그렇지 않으면 다음으로 넘어갑니다. 전화 번호부가 순서가 지정되지 않았기 때문에 이런 식으로해야합니다 (어쨌든 전화 번호로).

따라서 전화 번호 (역방향 조회)로 이름을 찾으려면 :

• 모범 사례 : O (1);
• 예상 사례 : O (n) (500,000) 과
• 최악의 경우 : O (n) (1,000,000).

• 모범 사례 : O (1);
• 예상 사례 : O (n) (500,000) 과
• 최악의 경우 : O (n) (1,000,000).

이것은 컴퓨터 과학에서 매우 유명한 문제이며 언급 할 가치가 있습니다. 이 문제에는 N 개의 마을이 있습니다. 각 도시는 특정 거리의 도로를 통해 하나 이상의 다른 도시와 연결되어 있습니다. Traveling Salesman 문제는 모든 마을을 방문하는 가장 짧은 여행을 찾는 것입니다.

간단하게 들리나요? 다시 생각 해봐.

모든 쌍 사이에 도로가있는 3 개의 마을 A, B, C가있는 경우 다음을 수행 할 수 있습니다.

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

• A → B → C
• A → C → B
• B → C → A
• B → A → C
• C → A → B
• C → B → A

글쎄, 실제로 이것들 중 일부는 동등하기 때문에 그보다 적습니다 (A → B → C 및 C → B → A는 동일합니다. 예를 들어, 동일한 도로를 사용하기 때문에 반대로).

실제로 3 가지 가능성이 있습니다.

• 이것을 4 개의 마을로 가져 가면 12 개의 가능성이 있습니다.
• 5로 60입니다.
• 6은 360이됩니다.

• 이것을 4 개의 마을로 가져 가면 12 개의 가능성이 있습니다.
• 5로 60입니다.
• 6은 360이됩니다.

이것은 계승 이라고하는 수학적 연산의 함수입니다. 원래:

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 10 ⁶⁴

• 5! = 5 × 4 × 3 × 2 × 1 = 120
• 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720
• 7! = 7 × 6 × 5 × 4 × 3 × 2 × 1 = 5040
• …
• 25! = 25 × 24 ×… × 2 × 1 = 15,511,210,043,330,985,984,000,000
• …
• 50! = 50 × 49 ×… × 2 × 1 = 3.04140932 × 10 ⁶⁴

따라서 Traveling Salesman 문제의 Big-O는 O (n!) 또는 팩토리얼 또는 조합 복잡성 입니다.

200 개의 마을에 도착할 때까지 우주에 기존 컴퓨터의 문제를 해결할 시간이 충분하지 않습니다.

생각할 것.

제가 빠르게 언급하고 싶었던 또 다른 점은 O (n ^a ) 의 복잡성을 가진 모든 알고리즘이 다항식 복잡성 을 가지고 있거나 다항식 시간 에서 풀 수 있다는 것입니다.

O (n), O (n ² ) 등은 모두 다항식 시간입니다. 일부 문제는 다항식 시간에 풀 수 없습니다. 이 때문에 세상에서 어떤 것들이 사용됩니다. 공개 키 암호화 가 대표적인 예입니다. 매우 큰 수의 두 개의 소인수를 찾는 것은 계산적으로 어렵습니다. 그렇지 않으면 우리가 사용하는 공개 키 시스템을 사용할 수 없습니다.

어쨌든, Big O (개정 됨)에 대한 설명입니다.

출처 : https://stackoverflow.com/questions/487258/what-is-a-plain-english-explanation-of-big-o-notation