O (log n)은 항상 O (n)보다 빠릅니다.

Question

다른 복잡도로 같은 결과를 계산하는 2 개의 algorthim이있는 경우 O (log n)은 항상 빠릅니까? 그렇다면 설명해주십시오. BTW 이것은 배정 문제가 아닙니다.

Answer 1

아니요 하나의 알고리즘이 N/100에서 실행되고 다른 알고리즘이 (log N)*100에서 실행되는 경우 두 번째 알고리즘은 더 작은 입력 크기의 경우 느려집니다. 점근선 복잡성은 입력 크기가 무한대로 갈 때 실행 시간의 동작에 관한 것입니다.

Answer 2

아니요, 항상 더 빠를 수는 없습니다. 하지만 문제의 크기가 커지면, 은 결국이고 O (log n) 알고리즘은 O (n) 알고리즘보다 빠릅니다.

일반적으로 O (log n) 알고리즘이 O (n) 알고리즘을 추월하는 지점은 매우 빠르게 나타납니다. O (n)과 O (n^2) 사이에 큰 차이가있는 것처럼 O (log n)과 O (n)에는 큰 차이가 있습니다. 혹시 존 벤틀리에 의해 프로그래밍 진주을 읽을 수있는 기회를 가질 경우

, 그가 O에 대해 O (n)이 알고리즘을 구덩이가있는 멋진 장이 (가 N^2)에 가능한 모든 일을 하나, O (n^2)에게 이점을주십시오. (그는 Alpha에서 C로 O (n^2) 알고리즘을 코딩하고, 오래된 Z80 또는 뭔가에 대해 해석 된 BASIC에서 O (n) 알고리즘을 약 1MHz로 실행합니다.) O (n) 알고리즘이 O (n^2)를 추월합니다.

그러나 때때로 복잡한 알고리즘을 발견 할 수 있습니다. 복잡한 알고리즘은 단순한 알고리즘보다 약간 낫습니다. 이 경우 맹목적으로 더 나은 빅 -O를 가진 알고리즘을 선택하지 마십시오. 매우 큰 문제에 대해서만 더 빠르다는 것을 알 수 있습니다.