인용문은 다소 모호하고 정확하지 않습니다. 해석 할 수있는 방법은 3 가지 이상 있습니다.

문자 그대로의 수학적 요점은 크기 제한이있는 인스턴스에만 관심이 있다면 가능한 많은 인스턴스가 있다는 것입니다. 예를 들어, 최대 100 개의 정점에는 유한하게 많은 그래프가 있습니다. 유한 한 수의 인스턴스 만있는 경우 원칙적으로 가능한 모든 인스턴스에 대한 모든 응답의 룩업 테이블을 구성하여 문제를 해결할 수 있습니다. 이제 입력이 너무 크지 않은지 먼저 확인하여 정답을 찾을 수 있습니다 (일정 시간이 걸립니다 : 입력이 k 보다 긴 경우 케이

$k$

$k$유효하지 않은 경우) 표에서 답변을 찾아보십시오. 시간이 오래 걸립니다. 표에 고정 된 수의 항목이 있습니다. 그러나 테이블의 실제 크기는 아마도 엄청나게 클 수도 있습니다. 백 정점에는 유한 한 수의 그래프 만 있다고했는데 사실입니다. 유한 한 수가 관측 가능한 우주의 원자 수보다 더 크다는 것입니다.

더 실용적인 점은 알고리즘의 실행 시간이 라고 말할 때  일부 상수 C에 대해 무증상 c n 2 단계  임을 의미합니다 . 즉, 모든 n ≥ n 0 에 대해 알고리즘이 대략 c n 2 단계를 취하도록 일정한 n 0이 있습니다. 그러나 아마도 n 0 = 100 , 000 , 000Θ ( n2)

$\mathrm{\Theta }(n^2)$

$\Theta(n^2)$ c n2

$c{n}^2$

$cn^2$기음

$C$

$C$엔0

$n_0$

$n_0$n ≥ n0

$n\ge n_0$

$n\geq n_0$c n2

$c{n}^2$

$cn^2$엔0= 100 , 000 , 000

$n_0=100,000,000$

$n_0=100,000,000$그보다 훨씬 작은 크기의 인스턴스에만 관심이 있습니다. 점근 2 차 경계는 소규모 인스턴스에도 적용되지 않을 수 있습니다. 운이 좋을 수도 있고 작은 입력에서 더 빠를 수도 있습니다 (또는 운이 좋지 않아 느려질 수도 있습니다). 예를 들어 small  , n 2 < 1000 n 인 경우 상수가 나쁜 선형 알고리즘보다 상수가 좋은 2 차 알고리즘을 실행하는 것이 좋습니다. 실제 사례는 무증상으로 가장 효율적인 행렬 곱셈 알고리즘 ( 시간이 O ( n 2.3729 )로 실행되는 Coppersmith-Winograd의 변형 )이 Strassen의 O 때문에 실제로 거의 사용되지 않는다는 것입니다엔

$n$

$n$엔2< 1,000 N

$n^2<1000n$

$n^2 < 1000n$영형(n2.3729)

$O(n^{2.3729})$

$O(n^{2.3729})$ 알고리즘은 행렬이 실제로 크지 않으면 더 빠릅니다.O (n2.8074)

$O(n^{2.8074})$

$O(n^{2.8074})$

세 번째 요점은  이 작 으면 n 2 및 심지어 n 3  이 작다는 것입니다. 예를 들어, 수천 개의 데이터 항목을 정렬해야하고 한 번만 정렬해야하는 경우 정렬 알고리즘으로 충분합니다. a Θ ( n 2 )엔

$n$

$n$엔2

$n^2$

$n^2$엔삼

$n^3$

$n^3$Θ (n2)

$\mathrm{\Theta }(n^2)$

$\Theta(n^2)$알고리즘은 여전히 ​​데이터를 정렬하기 위해 수천만 개의 명령이 필요할 것인데, 이는 초당 수십억 개의 명령을 수행 할 수있는 CPU에서 전혀 시간이 걸리지 않습니다. 좋아, 메모리 액세스도 있지만 느린 알고리즘조차도 1 초도 걸리지 않으므로 간단하고 느린 알고리즘을 사용하고 복잡하고 빠른 알고리즘을 사용하고 번개가 빠른 것을 찾는 것보다 낫습니다. 그러나 버그가 있고 실제로 데이터를 올바르게 정렬하지 않습니다.

---

답변