algorithm 표기법 8 살짜리 빅 오?




파이썬 시간 복잡도 (20)

Big-O 표기법이 코드에 대해 큰 의미를 두는 것은 그것이 작동하는 "물건"의 양을 두 배로 늘릴 때 확장 방법입니다. 다음은 구체적인 예입니다.

Big-O       |  computations for 10 things |  computations for 100 things
----------------------------------------------------------------------
O(1)        |   1                         |     1
O(log(n))   |   3                         |     7
O(n)        |  10                         |   100
O(n log(n)) |  30                         |   700
O(n^2)      | 100                         | 10000

그래서 O (n log (n))와 O (n ^ 2) 인 버블 정렬 인 quicksort를 사용하십시오. 10 가지를 정렬 할 때 quicksort는 버블 정렬보다 3 배 빠릅니다. 하지만 100 가지를 정렬하면 14 배 빠릅니다! 분명히 가장 빠른 알고리즘을 선택하는 것이 중요합니다. 백만 행이있는 데이터베이스를 검색하면 쿼리를 실행하는 데 걸리는 시간과 0.2 초를 비교하는 데 걸리는 시간을 의미 할 수 있습니다.

고려해야 할 또 다른 사항은 무어의 법칙이 도움이되지 못하는 잘못된 알고리즘이라는 것입니다. 예를 들어 O (n ^ 3)이라는 과학적 계산이 있고 하루에 100 개를 계산할 수있는 경우 프로세서 속도를 두 배로 늘리면 하루에 125 가지만 얻을 수 있습니다. 그러나 그 계산을 O (n ^ 2)로 치면 하루에 1000 가지 일을하고있는 것입니다.

설명 : 사실, Big-O는 동일한 특정 크기 지점에서 서로 다른 알고리즘의 비교 성능에 대해서는 언급하지 않고 오히려 서로 다른 크기 지점에서 동일한 알고리즘의 비교 성능에 대해 말합니다.

                 computations     computations       computations
Big-O       |   for 10 things |  for 100 things |  for 1000 things
----------------------------------------------------------------------
O(1)        |        1        |        1        |         1
O(log(n))   |        1        |        3        |         7
O(n)        |        1        |       10        |       100
O(n log(n)) |        1        |       33        |       664
O(n^2)      |        1        |      100        |     10000

이 질문에는 이미 답변이 있습니다.

나는 이것이 내 코드에 어떤 의미가 있는지에 대해 더 많이 묻고있다. 나는 개념을 수학적으로 이해하고 있으며, 개념적으로 의미하는 것을 내 머리 속으로 감싸는 데 어려움을 겪고 있습니다. 예를 들어 데이터 구조에서 O (1) 연산을 수행하는 경우 더 많은 항목이 있기 때문에 수행해야하는 연산의 양은 증가하지 않는다는 것을 알고 있습니다. 그리고 O (n) 연산은 각 요소에 대해 일련의 연산을 수행한다는 것을 의미합니다. 누군가 여기서 공백을 채울 수 있을까요?

  • O (n ^ 2) 연산은 정확히 무엇을할까요?
  • 그리고 연산이 O (n log (n))이면 그것은 무엇을 의미합니까?
  • 그리고 누군가는 O (x!)를 쓰기 위해 균열을 피워야합니까?

특정 크기의 문제를 해결할 수있는 컴퓨터가 있다고 가정합니다. 이제 성능을 몇 배로 높일 수 있다고 상상해보십시오. 각각의 배증으로 얼마나 큰 문제를 해결할 수 있습니까?

우리가 두 배의 크기의 문제를 풀 수 있다면 그것은 O (n)입니다.

우리가 하나가 아닌 어떤 승수를 가지고 있다면 그것은 일종의 다항식 복잡성입니다. 예를 들어, 각 배가가 문제 크기를 약 40 %까지 증가시킬 수 있다면 O (n ^ 2)이고 약 30 %는 O (n ^ 3) 일 것입니다.

우리가 단지 문제의 크기에 더하면 지수가 더 나빠집니다. 예를 들어, 각 doubling이 우리가 더 큰 문제 1을 풀 수 있다면, 그것은 O (2 ^ n)입니다. 128 비트 키는 64 비트만큼 많은 처리량을 필요로합니다. (암호화 키를 무리하게 강요하는 것은 합리적인 크기의 키로는 불가능합니다.


8 살짜리 log (n)은 길이 n을 1로 잘라야한다는 것을 의미합니다. 크기 n = 1로 내려 가기 위해 두 번 로그인하십시오 : p

O (n log n)은 일반적으로 정렬입니다. O (n ^ 2)는 일반적으로 모든 요소 쌍을 비교합니다.


Jon Bentley의 대부분의 책 (예 : 프로그래밍 진주 )은 실제로 실용적인 방식으로 그러한 것들을 다루고 있습니다. 그에게 주어진 이 이야기 에는 퀵 소트 (quicksort) 같은 분석이 포함되어 있습니다.

이 질문에 완전히 관련되어 있지는 않지만 Knuth는 재미있는 아이디어를 내놓았습니다 . 고교 수학 수업에서 Big-O 표기법을 가르치는 것입니다.


시각화하는 것이 유용 할 수 있습니다.

또한 LogY / LogX 스케일에서 n 1/2 , n, n 2 함수는 모두 직선 처럼 보이지만 LogY / X 스케일 2 n , e n , 10 n 은 직선과 n입니다. 선형입니다 ( n log n 처럼 보입니다).


don.neufeld의 답은 매우 좋지만 아마도 두 부분으로 설명 할 수 있습니다. 첫째, 대부분의 알고리즘이 들어있는 O ()의 거친 계층이 있습니다. 그런 다음, 각각의 시간 복잡도의 전형적인 알고리즘이 무엇을하는지 그 스케치를 생각해 볼 수 있습니다.

실용적인 목적을 위해 유일한 O ()의 문제는 다음과 같습니다.

  • O (1) "일정 시간"- 필요한 시간은 입력 크기와 무관합니다. 대략적인 범주로, 해시 검색과 Union-Find 같은 알고리즘을 포함 할 것입니다. 실제로 이들 중 어느 것도 O (1)는 아니지만.
  • O (log (n)) "대수"- 더 큰 입력을 받으면 속도가 느려지지만 입력이 상당히 커지면 걱정할만큼 충분히 변하지 않을 것입니다. 합리적인 크기의 데이터로 런타임이 정상이라면 원하는만큼 많은 추가 데이터를 사용하여 늪을 잠글 수 있으며 그래도 괜찮습니다.
  • O (n) "linear"- 입력이 많을수록 더 오랜 시간이 소요됩니다. 입력 크기의 세 배는 대략 세 배나 오래 걸립니다.
  • O (n log (n)) "2 차보다 낫다"- 입력 크기가 커지게되지만 여전히 관리가 가능합니다. 알고리즘은 괜찮은 것 같습니다. 선형 시간으로 해결할 수있는 문제보다 기본 문제가 더 어렵습니다 (입력 데이터와 관련하여 결정이 현지화되지 않음). 입력 크기가 커지면 아키텍처를 변경하지 않고 (예 : 밤새 배치 계산으로 이동하거나 프레임 당 일을하지 않음) 두 배의 크기를 처리 할 수 ​​있다고 가정하지 마십시오. 비록 입력 크기가 약간 증가해도 괜찮습니다. 배수에주의하십시오.
  • O (n ^ 2) "quadratic"- 실제로는 입력의 특정 크기만큼만 작동하므로 입력 크기에주의하십시오. 또한 알고리즘이 빨라질 수도 있습니다 - 필요한 알고리즘을 제공하는 O (n log (n)) 알고리즘이 있는지 생각해보십시오. 일단 여기에 계시다면, 우리가 타고난 놀라운 하드웨어에 대해 매우 고맙게 생각합니다. 오래 전에, 당신이하려고하는 것은 모든 실제적인 목적을 위해 불가능했을 것입니다.
  • O (n ^ 3) "입방체"- O (n ^ 2)와는 다른 모든 것을 정 성적으로 나타내지는 않습니다. 같은 주석이 적용됩니다. 좀 더 똑똑한 알고리즘을 사용하면이 시간을 O (n ^ 2 log (n)) 또는 O (n ^ 2.8 ...)와 같이 더 작게 줄일 수 있지만, 다시 한번, 문제의 가치가되지 않습니다. (당신은 이미 실용적인 입력 크기가 제한되어 있기 때문에 더 똑똑한 알고리즘에 필요한 상수 요소가 실용적인 경우에 이점을 얻지 못할 것입니다. 또한 사고가 느리므로 컴퓨터를 씹으면 시간이 절약됩니다 사무용 겉옷.)
  • O (2 ^ n) "지수"- 문제는 근본적으로 계산적으로 어렵거나 바보입니다. 이러한 문제는 그들에게 인식할만한 맛을줍니다. 귀하의 입력 크기는 매우 엄격한 제한으로 제한됩니다. 당신은 당신이 그 한계에 들어 맞는지를 빨리 알게 될 것입니다.

그리고 그게 다야. 이들 사이에 적합하거나 (O (2 ^ n)보다 큼) 많은 다른 가능성이 있지만 실제로는 실제로 발생하지 않으며 정 성적으로 이들 중 하나와 많이 다릅니다. 큐빅 알고리즘은 이미 약간의 확장이 있습니다. 나는 그것들을 언급할만한 가치가있을만큼 충분히 자주 뛰어 왔기 때문에 그것들을 포함 시켰을뿐입니다 (예. 행렬 곱셈).

이러한 알고리즘 클래스에서 실제로 어떤 일이 발생합니까? 글쎄, 나는 당신들이 좋은 시작을 가지고 있다고 생각하지만,이 특성들에 맞지 않는 많은 예들이있다. 그러나 위의 경우, 일반적으로 다음과 같이 나타납니다.

  • O (1) - 입력 데이터를 고정 된 크기의 청크로만보고 있으며 그 중 아무 것도 볼 수 없습니다. 예 : 정렬 된 목록의 최대 값.
    • 또는 입력 크기가 제한되어 있습니다. 예 : 두 개의 숫자를 더합니다. (N 숫자의 추가는 선형 시간입니다.)
  • O (log n) - 입력의 각 요소는 입력의 나머지 부분을 무시할만큼 충분히 알려줍니다. 예 : 바이너리 검색에서 배열 요소를 보면 그 값은 아무 것도 보지 않고 배열의 "절반"을 무시할 수 있음을 알려줍니다. 또는 비슷한 요소로 보면,보아야 할 요소가 남아있는 입력의 일부를 요약 할 수 있습니다.
    • 반쪽에는 특별한 것이 없습니다. 각 단계에서 입력의 10 % 만 무시할 수 있다면 여전히 로그입니다.
  • O (n) - 입력 요소 당 고정 된 양의 작업을 수행합니다. (하지만 아래 참조).
  • O (n log (n)) - 몇 가지 변형이 있습니다.
    • 입력을 두 개의 말뚝 (선형 시간 이상)으로 나누고 각 말뚝에서 문제를 독립적으로 해결 한 다음 두 말뚝을 결합하여 최종 솔루션을 만들 수 있습니다. 두 더미의 독립성이 중요합니다. 예 : 고전적인 재귀 합병.
    • 데이터에 대한 선형 시간을 모두 통과하면 솔루션의 절반까지 도달 할 수 있습니다. 예 : 각 분할 단계에서 각 요소의 최종 정렬 위치까지의 최대 거리를 생각하면 quicksort입니다 (예, 축퇴 피벗 선택 때문에 축퇴가 실제로 O (n ^ 2)임을 알 수 있습니다.) 실제로 말하면, 내 O (n log (n)) 카테고리에 속합니다.
  • O (n ^ 2) - 모든 입력 요소 쌍을 살펴 봐야합니다.
    • 그렇지 않으면, 당신은 그렇게 생각하고 잘못된 알고리즘을 사용하고 있습니다.
  • O (n ^ 3) - 음 ... 나는 이것들에 대해 잘 알지 못한다. 아마 다음 중 하나 일 것입니다.
    • 당신은 행렬을 곱하고 있습니다.
    • 당신은 모든 입력 쌍을보고 있지만, 모든 입력을 다시 살펴 봐야합니다.
    • 입력의 전체 그래프 구조가 관련성이 있습니다.
  • O (2 ^ n) - 가능한 모든 입력 부분을 고려해야합니다.

이들 중 어느 것도 엄격합니다. 특히 선형 시간 알고리즘 (O (n))이 아닙니다 : 모든 입력을 살펴본 다음 그 중 절반, 그 중 절반 등을 살펴야하는 여러 가지 예를 생각해 낼 수 있습니다. - 입력 쌍을 접어서 출력에 재귀 적으로 사용합니다. 위의 설명에 맞지 않습니다. 각 입력을 한 번 보지 않아도 선형 시간으로 나옵니다. 여전히 시간의 99.2 % 인 선형 시간은 각 입력을 한 번 보는 것을 의미합니다.


어떤 이유로 아직 손대지 않은 한 가지 :

O (2 ^ n) 또는 O (n ^ 3) 또는 다른 불쾌한 값을 가진 알고리즘을 볼 때 종종 수용 가능한 성능을 얻으려면 문제에 대한 불완전한 대답을 받아 들여야 할 것입니다.

최적화 문제를 다룰 때는 이와 같은 문제를 해결하는 올바른 해결책이 일반적입니다. 합리적인 기간 내에 전달 된 거의 정확한 답변은 기계가 먼지가 날 때까지 오랫동안 전달 된 정답보다 낫습니다.

체스를 고려해보십시오. 정확한 해결책이 무엇인지는 정확히 알지 못하지만 O (n ^ 50) 또는 그보다 더 나쁜 것 같습니다. 이론적으로 모든 컴퓨터가 정답을 실제로 계산하는 것은 불가능합니다. 우주의 모든 입자를 컴퓨팅 요소로 사용하여 우주 수명 동안 가능한 한 최소 시간 내에 작업을 수행하더라도 여전히 많은 0이 남아 있습니다 . 양자 컴퓨터가 그것을 해결할 수 있는지 여부는 또 다른 문제입니다.


O (n log n)을 이해하려면 log n은 n의 log-base-2를 의미한다는 것을 기억하십시오. 그런 다음 각 부분을 살펴보십시오.

O (n)은 세트의 각 항목을 조작 할 때 다소 차이가 있습니다.

O (log n)은 연산 수가 2를 올리는 지수와 같을 때 항목 수를 얻는 경우입니다. 예를 들어, 이진 검색은 집합을 반 로그 n 번 잘라야합니다.

O (n log n)은 조합입니다. 집합의 각 항목에 대해 이진 검색 행을 따라 뭔가를 수행하고 있습니다. 효율적인 정렬은 항목 당 하나의 루프를 수행하고 각 루프에서 항목이나 그룹을 넣을 적절한 위치를 찾기 위해 좋은 검색을 수행하는 방식으로 작동합니다. 따라서 n * log n.


내가 비 기술적 인 친구들에게 설명하는 방법은 이렇습니다 :

여러 자리 추가를 고려하십시오. 좋은 구식, 연필 및 종이 추가. 당신이 7-8 세 때 배웠던 종류. 두 개의 3 자리 또는 4 자리 숫자가 주어지면, 그들이 합쳐진 것을 쉽게 찾을 수 있습니다.

내가 두 자리 100 자리 숫자를주고, 무엇을 더할 지 물어 보면, 연필과 종이를 써야한다고해도 그것을 알아내는 것은 매우 간단 할 것입니다. 밝은 아이는 단 몇 분 안에 그러한 추가 작업을 할 수 있습니다. 이것은 약 100 번의 조작 만 필요합니다.

자, 다중 숫자 곱셈을 고려하십시오. 당신은 아마도 약 8 ~ 9 세에 그것을 배웠을 것입니다. 당신은 (잘하면) 그것의 뒤에 기계공을 배우는 많은 반복 훈련을했다.

자, 내가 똑같은 두 자리 100 자리 숫자를주고 상환하라는 말을했다고 상상해보십시오. 이것은 훨씬 더 힘든 작업으로, 몇 시간이 걸릴 것이고, 실수없이 할 수는 없을 것입니다. 그 이유는 (이 버전의) 곱셈은 O (n ^ 2)입니다. 맨 아래 번호의 각 숫자에 맨 위 숫자의 각 숫자가 곱해 져야하며, 약 n ^ 2 개의 조작이 남아 있어야합니다. 100 자리 숫자의 경우 10,000 곱셈입니다.


위의 게시물에 대한 몇 가지 의견에 응답하기 위해 :

Domenic - 저는이 사이트에 있습니다. 보행자를위한 것이 아니라 프로그래머로서 우리는 일반적으로 정밀도에주의를 기울이기 때문입니다. O () 표기법을 잘못 사용하여 일부 사람들이 여기에서 한 스타일에서 의미가 없게 만든다. 우리는 여기에 사용 된 규칙에 따라 n ^ 2 단위의 시간을 O (n ^ 2)로 취하는 것을 말할 수 있습니다. O ()를 사용하면 아무 것도 추가되지 않습니다. 일반적인 사용법과 수학적 정확성 사이의 작은 불일치 만이 아닙니다. 의미있는 것과 그렇지 않은 것의 차이입니다.

나는이 용어를 정확하게 사용하는 많은 훌륭한 프로그래머를 많이 알고 있습니다. '오, 우리는 프로그래머이기 때문에 우리는 신경 쓰지 않습니다'라고 말하면 전체 기업을 저렴하게 만듭니다.

onebyone - 글쎄, 내가 당신의 요점을 알고 있지만. 임의로 큰 n에 대한 O (1)는 아니며 O ()의 정의입니다. 단지 O ()가 bounded n에 대한 적용 가능성을 제한한다는 것을 보여주기 위해 간다. 여기서 우리는 실제로 그 수의 경계 대신 걸리는 단계의 수에 대해 이야기하고자한다.


그것에 대해 생각하는 한 가지 방법은 다음과 같습니다.

O (N ^ 2)는 모든 요소에 대해 다른 모든 요소 (예 : 요소를 비교하는 것)를 사용하여 작업하는 것을 의미합니다. 버블 정렬은 이것의 한 예입니다.

O (N log N)은 모든 요소에 대해 요소의 로그 N 만 살펴 봐야한다는 것을 의미합니다. 이는 대개 효율적인 선택을 할 수있는 요소에 대해 알고 있기 때문에 발생합니다. 가장 효율적인 정렬은 병합 정렬과 같은 예입니다.

O (N!)는 N 개의 모든 가능한 순열에 대해 무언가를하는 것을 의미합니다. 여행 세일즈맨은 이것의 한 예입니다. N! 노드를 방문하는 방법, 그리고 무차별 대입 솔루션은 모든 가능한 순열의 총 비용을 살펴 최적의 순열을 찾는 것입니다.


log (n)은 로그 증가를 의미합니다. 예를 들어 알고리즘을 나누고 정복하는 것입니다. 배열에 1000 개의 정렬 된 숫자 (예 : 3, 10, 34, 244, 1203 ...)가 있고 목록에서 숫자를 검색하려는 경우 (해당 위치 찾기), 당신이 찾는 것보다 낮 으면 750으로 점프하십시오. 당신이 찾는 것보다 높으면 250으로 점프하십시오. 그리고 나서 당신이 당신의 가치 (그리고 열쇠)를 찾을 때까지 그 과정을 반복하십시오. 우리가 검색 공간의 절반을 뛰어 넘을 때마다 숫자 3004가 숫자 5000 이상일 수 없다는 것을 알기 때문에 다른 많은 값들을 테스트해볼 수 있습니다. (이것은 정렬 된리스트입니다).

n log (n)은 n * log (n)을 의미합니다.


질문에 진지하게 남아 있기 위해 내가 8 살짜리 아이에게 대답 할 것 인 방식으로 질문에 답할 것입니다.

아이스크림 판매자가 규칙적인 방식으로 정렬 된 여러 모양의 아이스크림 (예 : N)을 준비한다고 가정합니다. 중간에있는 아이스크림 먹고 싶다.

사례 1 : - 당신은 모든 아이스크림을 그것보다 작게 먹었을 때만 아이스크림을 먹을 수 있습니다. 준비된 모든 아이스크림의 절반을 먹어야합니다. (입력). 입력의 크기에 따라 직접 해결책이 나올 것입니다. 주문 o (N)

사례 2 : - 중간에 아이스크림을 직접 먹을 수 있습니다.

해결책은 O (1)

사례 3 : 아이스크림을 먹을 수 있습니다. 아이스크림을 먹은 경우에만 아이스크림을 먹을 때마다 아이스크림을 먹을 수 있습니다. 아이스크림을 먹을 때마다 아이스크림을 먹을 수 있습니다. + N + N ....... (N / 2) 번 솔루션은 O (N2)


그것을 레고 블록 (n)을 수직으로 겹쳐서 점프하는 것으로 생각하십시오.

O (1)은 각 단계마다 아무 것도하지 않음을 의미합니다. 높이는 동일하게 유지됩니다.

O (n)은 각 단계에서 c 블록을 스택하는 것을 의미합니다. 여기서 c1은 상수입니다.

O (n ^ 2)는 각 단계에서 c2 xn 블록을 쌓는 것을 의미합니다. 여기서 c2는 상수이고 n은 스택 된 블록의 수입니다.

O (nlogn)는 각 단계에서 c3 xnx log n 블록을 쌓는 것을 의미합니다. 여기서 c3은 상수이고 n은 스택 된 블록의 수입니다.


아니오, O (n) 알고리즘은 각 요소에 대해 연산을 수행한다는 의미는 아닙니다. Big-O 표기법을 사용하면 실제 시스템과 독립적으로 알고리즘의 "속도"에 관해 이야기 할 수 있습니다.

O (n)은 알고리즘의 입력 시간이 선형 적으로 증가하는 시간을 의미합니다. O (n ^ 2)는 알고리즘이 걸리는 시간이 입력의 제곱으로 커짐을 의미합니다. 기타 등등.


이것은 너무 수학적 일지 모르지만, 여기 내 시도입니다. (저는 수학자입니다.)

무언가가 O ( f ( n ))이면, n 요소의 실행 시간은 A f ( n ) + B (클록주기 또는 CPU 연산에서 측정)와 같습니다. 특정 구현에서 발생하는 상수 AB 가 있음을 이해하는 것이 중요합니다. B 는 본질적으로 작업의 "일정한 오버 헤드"를 나타냅니다. 예를 들어 콜렉션의 크기에 의존하지 않는 일부 사전 처리가 있습니다. A 는 실제 아이템 처리 알고리즘의 속도를 나타냅니다.

그러나 키는 큰 O 표기법을 사용하여 무언가가 얼마나 확장 될지 파악합니다. 그 상수는 실제로 중요하지 않습니다. 10-10000 개의 항목으로 확장하는 방법을 파악하려는 경우 누가 일정한 오버 헤드 B 를 염려합니까? 비슷하게, 다른 관심사 (아래 참조)는 확실히 곱셈 상수 A 의 중요도를 능가 할 것입니다.

그래서 실제 거래는 f ( n )입니다. fn 과 함께 전혀 증가하지 않으면, 예를 들어 f ( n ) = 1이면, 당신은 환상적으로 확장 할 것입니다 - 당신의 실행 시간은 언제나 A + B가 될 것입니다. fn , 즉 f ( n ) = n 으로 선형 적으로 커지면, 예상되는 시간만큼 실행 시간이 확장 될 것입니다. 사용자가 10 개의 요소를 10 ns 기다리는 경우 10000 ns를 기다립니다 요소 (상수를 무시). 그러나 n2 처럼 빠르게 성장하면 문제가 생깁니다. 더 큰 컬렉션을 얻으면 상황이 너무 느리게 시작됩니다. f ( n ) = n log ( n )은 좋은 절충안입니다 : 선형 스케일링을 제공하는 것처럼 조작을 간단하게 할 수는 없지만, f 보다 훨씬 더 커질 수 있도록 작업을 줄 였습니다. ( n ) = n2 이다.

실질적으로 다음과 같은 좋은 예가 있습니다.

  • O (1) : 배열에서 요소를 검색. 우리는 그것이 기억 속에있는 곳을 정확히 알고 있습니다, 그래서 우리는 그것을 얻습니다. 컬렉션에 10 개 항목 또는 10000 개가 있는지 여부는 중요하지 않습니다. 그것은 여전히 ​​색인 (말) 3입니다. 그래서 우리는 메모리에서 위치 3으로 점프합니다.
  • O ( n ) : 연결된 목록에서 요소를 검색합니다. 여기서 A = 0.5입니다. 평균적으로 찾고있는 요소를 찾기 전에 링크 된 목록의 1/2을 거쳐야 할 것이기 때문입니다.
  • O ( n 2 ) : 다양한 "멍청한"분류 알고리즘. 일반적으로 전략은 각 요소 ( n )에 대해 다른 모든 요소 (두 번째 n , n 2 )를보고 올바른 위치에 놓습니다.
  • O ( n log ( n )) : 다양한 "스마트"분류 알고리즘. 컬렉션에있는 다른 모든 사람들과 비교하여 지능적으로 자신을 분류하려면 10 개의 요소로 된 요소 컬렉션에서 10 개의 요소 만 살펴 봐야합니다. 왜냐하면 다른 모든 사람들 10 가지 요소를 보게 될 것이고 응급 행동은 바로 정렬되어 정렬 된 목록을 생성하기에 충분합니다.
  • O ( n !) : n에 비례하기 때문에 "모든 것을 시도하는"알고리즘! 주어진 문제를 푸는 n 요소의 가능한 조합. 따라서 모든 조합을 반복하고 시도한 다음 성공할 때마다 중지합니다.

거북이와 토끼 (거북이와 토끼)의 우화를 기억하나요?

장기적으로, 거북이가이기는하지만 단기간에 토끼가 이기게됩니다.

그것은 O (logN) (거북이) 대 O (N) (토끼)와 같습니다.

big-O에서 두 가지 방법이 다르다면 그 중 하나가 승리 할 N 수준이 있지만 big-O는 N이 얼마나 큰지에 대해 아무 것도 말하지 않습니다.


Ok - 여기에 몇 가지 좋은 답변이 있지만 거의 모든 것이 똑같은 실수를하는 것처럼 보입니다. 일반적인 사용법이 보편화되어 있습니다.

비공식적으로, 우리는 스케일링 팩터까지, 그리고 일부 n0보다 큰 모든 n에 대해 g (n)이 f (n)보다 경우 f (n) = O (g (n))이라고 씁니다. 즉, f (n) g (n)보다 빠르게 성장하지 않거나 g (n)에 의해 위에서부터 구속됩니다 . 이것은 f (n)이 얼마나 빨리 성장하는지에 대해서는 알려주지 않으며 g (n)보다 나쁘지 않을 것이라는 점을 제외하고는 우리에게 알려주지 않습니다.

구체적인 예 : n = O (2 ^ n). 우리는 n이 2 ^ n보다 훨씬 빨리 성장한다는 것을 알고 있습니다. 그래서 그것은 지수 함수에 의해 위에 묶여 있다고 말할 수있는 자격을줍니다. n과 2 ^ n 사이에는 많은 여유 공간이 있습니다. 따라서 매우 단단한 경계는 아니지만 여전히 합법적 인 경계입니다.

왜 우리 (컴퓨터 과학자)는 정확한 것이 아니라 경계를 사용합니까? a) 경계는 종종 증명하기가 더 쉽고 b) 알고리즘의 속성을 표현하기 위해 짧은 손을 제공하기 때문입니다. 내가 말하는 새 알고리즘이 O (n.log n)이면 최악의 경우 run-time이 n 입력에 대해 n.log n에 의해 제한 될 것임을 의미한다. 내가 최악의 경우를 의미하지 않을 때).

대신에 함수가 다른 함수와 똑같은 속도로 빠르게 성장한다고 말하면, 그 점을 만들기 위해 theta 를 사용합니다 (markdown에서 f (n)의 mean \ Theta를 T (f (n)이라고 씁니다) . T (g (n))는 위와 아래 에서 g (n)에 의해 바운딩되는 짧은 손이며, 다시 스케일링 요소까지 그리고 점근선 적으로입니다.

즉, f (n) = T (g (n)) == (g (n)) 및 g (n) = O (f (n))이다. 이 예에서, 2 ^ n! = O (n)이기 때문에 n! = T (2 ^ n)임을 알 수 있습니다.

왜 이것에 대해 걱정해야합니까? 당신의 질문에 '누군가가 O (x!)를 쓰려면 균열을 피워야할까요?'라고 쓰십시오. 기본적으로 여러분이 작성하는 모든 것은 계승 함수에 의해 위에 묶일 것이기 때문에 대답은 아니오입니다. quicksort의 실행 시간은 O (n!)입니다. 단단한 경계가 아닙니다.

여기 또 다른 차원의 미묘함이 있습니다. 일반적으로 우리는 O (g (n)) 표기법을 사용할 때 최악의 경우 입력 에 대해 이야기하고 있으므로 복합 문을 작성합니다. 최악의 경우 실행 시간은 g (n ) 단계, 다시 모듈로 스케일링 및 충분히 큰 n. 그러나 때때로 우리는 평균 의 실행 시간과 최상의 경우에 대해서 이야기하기를 원합니다.

바닐라 퀵 소트 (vanilla quicksort)는 좋은 예입니다. 그것은 최악의 경우에 T (n ^ 2)이다. (적어도 n ^ 2 단계는 걸리지 만 그 이상은 아니지만) 평균 경우의 T (n.log n), 즉 예상되는 단계는 n.log n에 비례합니다. 가장 좋은 경우에는 T (n.log n)입니다. 그러나 배열을 이미 정렬했는지 확인하여이를 향상시킬 수있는 경우 실행 시간이 가장 좋은 경우 T (n)가됩니다.

이것이이 범위의 실질적인 실현에 대한 귀하의 질문과 어떤 관련이 있습니까? 불행하게도 O () 표기법은 실제 구현이 처리해야하는 상수를 숨 깁니다. 예를 들어, T (n ^ 2) 연산에서 모든 가능한 요소 쌍을 방문해야한다고 말할 수 있지만, 우리는 몇 번이나 방문해야하는지 모릅니다. 엔). 그래서 우리는 모든 쌍을 10 번 또는 10 ^ 10 번 방문해야 할 수도 있습니다. T (n ^ 2) 문은 구별되지 않습니다. 하위 순서 함수도 숨겨져 있습니다. n ^ 2 + 100n = T (n ^ 2)이기 때문에 모든 요소 쌍을 한 번 방문하고 각 요소를 100 번 방문해야 할 수도 있습니다. O () 표기법 뒤에있는 개념은 충분히 큰 n에 대해서는 n ^ 2가 100n보다 훨씬 커져서 실행 시간에 100n의 영향을 알지 못하기 때문에 전혀 문제가되지 않는다는 것입니다. 그러나 우리는 종종 '충분하게 작다'는 식으로 대소 문자를 구별하여 실질적인 차이를 만듭니다.

예를 들어, quicksort (평균 비용 T (n.log n))와 heaport (평균 비용 T (n.log n))는 모두 평균 비용이 같은 정렬 알고리즘입니다. 그러나 quicksort는 일반적으로 힙보다 빠릅니다. heapsort가 quicksort보다 요소 당 몇 가지 비교를하기 때문입니다.

이것은 O () 표기법이 쓸모없고 부정확하다는 것을 말하는 것이 아닙니다. 그것은 작은 n을 위해 휘두르는 꽤 무딘 도구입니다.

(이 논문에 대한 마지막 메모로서 O () 표기법은 모든 기능의 성장을 설명한다는 것을 기억하십시오. 반드시 시간이 필요하지는 않으며, 메모리, 분산 시스템에서 교환 된 메시지 또는 병렬 알고리즘.)


기술 용어와 수학 개념을 제외하고 실제 8 살짜리 소년에 대한 설명을 실제로 작성하려고합니다.

O(n^2) 연산은 정확히 무엇을할까요?

당신이 파티에 있다면, 그리고 당신을 포함하여 파티에 n 명 있습니다. 얼마나 많은 핸드 셰이크가 걸리므로 모든 사람들이 핸드 셰이크를했습니다. 사람들이 어느 시점에서 핸드 셰이크를했는지 잊어 버릴 수도 있습니다.

참고 :이 값은 n^2 충분히 근접한 단순 항복 n(n-1) 에 가깝습니다.

그리고 수술이 있다면 그것은 무엇을 의미 O(n log(n))합니까?

좋아하는 팀이 승리했고, 그들은 선에 서서 n팀에 선수 가 있습니다 . 각 플레이어를 여러 번, 한 번, 몇 번, 얼마나 많은 숫자가 플레이어의 수에 있는지를 감안할 때, 모든 플레이어를 핸드 셰이크로 데려 갈 수있는 방법은 몇 가지가 있습니다 n.

참고 : 이렇게됩니다 n * log n to the base 10.

그리고 누군가는 쓰기 위해 균열을 피워야 O(x!)합니까?

당신은 부유 한 아이이고 옷장에 옷이 많이 있습니다. x각 유형의 옷을위한 서랍이 있습니다. 서랍은 서로 옆에 있으며, 첫 서랍에는 1 개의 항목이 있습니다. 각 서랍에는 서랍과 같은 수의 옷이 있습니다. 그 왼쪽과 하나 더, 그래서 당신은 1모자, 2가발, .. (x-1)바지, x셔츠 와 같은 것을 가지고 있습니다 . 이제 얼마나 많은 방법으로 각 서랍에서 하나의 항목을 사용하여 옷을 입을 수 있습니다.

참고 :이 예제는 어디 의사 결정 트리에 얼마나 많은 잎을 표현 number of children = depth을 통해 이루어집니다,1 * 2 * 3 * .. * x


  • 그리고 누군가는 O (x!)를 쓰기 위해 균열을 피워야합니까?

아니, 그냥 프롤로그를 써라. Prolog에 정렬 알고리즘을 작성하면 각 요소가 이전보다 커야하며 역 추적을 통해 정렬을 수행하면 O (x!)가됩니다. "순열 정렬"이라고도합니다.







metrics