algorithm - 표기법 - 자바 스크립트 시간 복잡도




프로그래머가 O(N ^ 2) 대신 O(N ^ 3)을 선호하는 이유는 무엇입니까? (5)

Big-O는 최악의 경우의 상한선입니다. QuickSort는 O (n ^ 2) 시간이고 MergeSort는 O (n lgn) 시간입니다. 그러나 QuickSort를 사용하는 사람들은 평균적으로 MergseSort보다 낮은 상수의 O (n lgn)이기 때문입니다.

나는 나의 마지막 시험을 위해 공부하고 있었다. 그리고 나는 그 대답을 발견 할 수 없다고하는 아카이브에 질문이있다.

하나의 알고리즘의 실행 시간의 성장 순서는 O (N ^ 2)이다. 두 번째 알고리즘의 실행 시간의 성장 순서는 O (N ^ 3)입니다. 프로그래머가 O (N ^ 2) 알고리즘 대신 O (N ^ 3) 알고리즘을 사용하려는 세 가지 이유 (논리적, 설득력)를 열거하십시오.


나는 다음 세 가지 이유를 생각할 수있다 :

  • 초기 구현이 쉽다.
  • 앞으로도 유지 보수가 용이합니다.
  • O (N ^ 3) 알고리즘은 O (N ^ 2) 알고리즘보다 공간 복잡성이 낮을 수 있습니다 (즉, 메모리 사용이 적음).

또 다른 것은, 일부 알고리즘은 큰 상수 요소를 가지고 있습니다. O (N^2) 는 사용하기에 실제적으로 사용하지 못하는 커다란 상수 요소를 가질 수 있습니다 ( N 이 Thorban이 친절하게 지적한만큼 작 으면)


아마도 # 1 이유 : O (N 2 ) 알고리즘은 충분히 높은 상수를 가지고 있기 때문에 작업의 크기에 대해 O (N 3 ) 버전이 빠릅니다.


하나의 알고리즘을 선택하는 유일한 이유는 실행 시간의 성장 순서가 아니기 때문입니다. 당신은 분석해야합니다 :

  • 구현하기가 얼마나 쉬운가요?
  • 필요한 공간
  • 실생활 투입물의 크기는 얼마입니까 (때로는 시간 차이는 현실에서는 결코 발생하지 않는 입력 크기에서만 나타납니다)




time-complexity