algorithm - 표기법 - 파이썬 시간 복잡도




8 살짜리 빅 오? (17)

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

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

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

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

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

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

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

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


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

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

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

O (n log 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 % 인 선형 시간은 각 입력을 한 번 보는 것을 의미합니다.


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

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


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

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

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

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


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

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

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

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

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


나는 neufeld의 대답을 좋아하지 만 O (n log n)에 대해 뭔가를 추가 할 수 있다고 생각합니다.

간단한 나누기 및 정복 전략을 사용하는 알고리즘은 아마도 O (log n)가 될 것입니다. 가장 간단한 예는 정렬 된 목록에서 무언가를 찾는 것입니다. 당신은 처음에는 시작하지 않고 그것을 스캔합니다. 중간에 가면, 뒤로 또는 앞으로 가야하는지, 마지막으로 보인 곳으로 도약 할지를 결정하고, 찾고있는 항목을 찾을 때까지 이것을 반복하십시오.

quicksort 또는 mergesort 알고리즘을 살펴보면 두 알고리즘 모두 정렬 할 목록을 절반으로 나누고 동일한 알고리즘을 반복적으로 사용하여 각 절반을 정렬 한 다음 두 절반을 다시 결합하는 방식을 사용하는 것을 볼 수 있습니다. 이런 종류의 재귀 적 분단과 정복 전략은 O (n log n)이 될 것입니다.

신중하게 생각하면 quicksort가 전체 n 개의 항목에 대해 O (n) 분할 알고리즘을 수행 한 다음 n / 2 개 항목에 대해 두 번 분할 한 다음 n / 4 항목에 대해 4 번 분할하는 O (n) 등등 ... 당신이 1 개의 품목에 n 개의 칸막이에 도착할 때까지 (퇴화된다). n을 반으로 나누어 1로 나눈 횟수는 대략 log n이며 각 단계는 O (n)이므로 재귀 적 분화와 정복은 O (n log n)입니다. Mergesort는 1 개의 항목의 n 개의 재조합으로 시작하여 두 개의 정렬 된 목록의 재조합이 O (n) 인 n 개의 항목의 1 개의 재조합으로 끝나는 다른 방법을 만듭니다.

O (n!) 알고리즘을 작성하는 흡연 균열에 관해서는 선택의 여지가없는 한 당신이 있습니다. 위에 주어진 여행 세일즈맨 문제는 그러한 문제 중 하나라고 생각됩니다.


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

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

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

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

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


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

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


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

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

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

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


이것들 중 많은 것들은 카드를 뒤섞는 것과 같은 무언가로 설명하기 쉽습니다.

스페이드의 에이스를 찾기 위해 전체 데크를 거쳐 카드 덱을 정렬 한 다음 스페이드 2 개를 찾기 위해 전체 덱을 통과하는 식으로하면 갑판이 이미 역순으로 정렬 된 경우 최하위 n ^ 2가됩니다. 52 장의 카드를 모두 52 번 보았습니다.

일반적으로 정말 나쁜 알고리즘은 반드시 의도적 인 것은 아니며 일반적으로 같은 세트에서 반복적으로 반복되는 다른 메소드 내부에서 선형 인 메소드를 호출하는 것과 같이 다른 것의 오용입니다.


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

무언가가 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 요소의 가능한 조합. 따라서 모든 조합을 반복하고 시도한 다음 성공할 때마다 중지합니다.

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

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

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

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

해결책은 O (1)

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


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

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

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

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


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

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





metrics