0
n, O (1)이 O (n)보다 빠르면 O (1) 알고리즘보다 O (n) 알고리즘을 선택할 때의 예모든 n, O (1)이 O (n)보다 빠를 때 O (1)에 대해 O (n) 선택?
A
답변
0
예를 들어 O O (n)이없는 동안 많은 메모리. 그리고 성능에 비해 메모리가 더 중요합니다.
+2
(_Please_ 함수의 점근 적 동작에 대한 표기법에주의하십시오. _small o_는 _argument가 엄격하게 더 큰 _을 의미합니다. o (1)의 알고리즘은 일정 시간 이내에 엄격하게 완료해야합니다.) 비 병렬 O (1) 알고리즘은 O (1) 메모리 만 건드릴 수 있습니다. 귀하의 추론은 O (n²) 이상 O (n)에 유효합니다. – greybeard
+0
@greybeard, 귀하의 요지를 이해하지만이 답변이 유효 할 수 있다고 생각합니다. 두 알고리즘 모두 O (1) 메모리를 사용한다고 가정합니다. 그러나 o (n)은 1 바이트를 사용하고 o (1) 알고리즘은 1000 바이트를 사용합니다. – Arashsoft
+0
@greybeard가 [big-O] (https : // ko) 대신 [little-o] (https://en.wikipedia.org/wiki/Big_O_notation#Related_asymptotic_notations) .wikipedia.org/wiki/Big_O_notation). 그들은 같은 것이 아닙니다. –
0
종종 실제 데이터는 시간 복잡성이 심한 알고리즘에 적합합니다. 예를 들어 O (n^2) 시간에 실행되는 거품 정렬은 거의 정렬 된 데이터에서 더 빠릅니다. 때때로, 상수 요인은 알고리즘이 너무 느려 실용적이지 않게 만들 수도 있습니다. big-O는 즉각적인 경우가 아니라 한계에서보다 효율적으로 작동하는 것을 처리합니다. 10000000의 상수 값을 갖는 O (1) 알고리즘은 n에 대해 1의 상수 값을 갖는 O (n) 알고리즘보다 상당히 느릴 것입니다. < 10000000.
그렇습니다. – jonrsharpe