하위 2 차 알고리즘과 2 차 알고리즘 간의 차이

Question

하위 2 차 알고리즘과 2 차 알고리즘간에 혼란 스럽습니다. 나는 이차원이 큰 O가 n square 일 때를 압니다. 그렇다면 sub-quadratic 알고리즘은 무엇입니까?

Answer 1

하위 준칙은 인 알고리즘을 지정하며 little-o notation을 사용합니다. 이는 복잡도가 n^2보다 훨씬 느려짐을 의미합니다. 그것은 선형에서 거의 2 차적인 것까지 될 수 있습니다.

Answer 2

평신도 용어로는 선형 및 2 차 수정 사이에 어떤 의미가 있습니다 (예 : n^2/logn).