[algorithm] 더 낮은 것보다 더 큰 big-O 시간 복잡성 알고리즘을 선호하는 경우가 있습니까?

낮은 O보다 복잡한 O 시간 복잡성을 가진 알고리즘을 선호하는 데는 여러 가지 이유가있을 수 있습니다.

• 대부분의 경우 Big-O 복잡성이 낮 으면 달성하기 어렵고 숙련 된 구현, 많은 지식 및 많은 테스트가 필요합니다.
• big-O는 상수에 대한 세부 사항을 숨 깁니다. 수행하는 알고리즘은 ( vs ) 10^5보다 big-O 관점에서 더 좋지만 가장 합리적인 경우 첫 번째 알고리즘 이 더 잘 수행됩니다. 예를 들어 행렬 곱셈의 가장 복잡한 점 은 상수가 너무 커서 (내 지식으로는) 계산 라이브러리에서 사용하지 않습니다.1/10^5 * log(n)O(1)O(log(n)nO(n^2.373)
• big-O는 큰 것을 계산할 때 의미가 있습니다. 세 개의 숫자 배열을 정렬 해야하는 경우 사용 O(n*log(n))또는 O(n^2)알고리즘 여부는 거의 중요하지 않습니다 .
• 때때로 소문자 시간 복잡성의 이점은 실제로 무시할 수 있습니다. 예를 들어, 데이터 구조 탱고 트리는O(log log N) 항목을 찾기에 시간 복잡성을 제공 하지만,에서 동일한 것을 찾는 이진 트리도 있습니다 O(log n). 엄청난 n = 10^20차이 의 경우 에도 무시할 수 있습니다.
• 시간의 복잡성이 전부는 아닙니다. 실행되고 메모리 O(n^2)가 필요한 알고리즘을 상상해보십시오 O(n^2). n이 실제로 크지 않은 경우 O(n^3)시간과 O(1)공간에 걸쳐 바람직 할 수 있습니다 . 문제는 오랫동안 기다릴 수 있지만 알고리즘과 함께 사용할 RAM을 충분히 찾을 수 있다는 것입니다.
• 병렬화는 분산 된 세계에서 좋은 기능입니다. 쉽게 병렬화 할 수있는 알고리즘이 있으며 전혀 병렬화되지 않는 알고리즘이 있습니다. 때로는 약간 더 복잡한 하나의 컴퓨터를 사용하는 것보다 복잡도가 높은 1000 개의 상용 컴퓨터에서 알고리즘을 실행하는 것이 좋습니다.
• 일부 장소 (보안)에서는 복잡성이 요구 될 수 있습니다. 누구도 굉장히 빨리 해시 할 수있는 해시 알고리즘을 원하지 않습니다.
• 이것은 복잡성 전환과 관련이 없지만 일부 보안 기능은 타이밍 공격 을 방지 하는 방식으로 작성되어야합니다 . 그것들은 대부분 같은 복잡성 클래스에 머물러 있지만 무언가를하기 위해서는 항상 더 나쁜 경우가되도록 수정됩니다. 한 예는 문자열이 같은지 비교하는 것입니다. 대부분의 응용 프로그램에서 첫 번째 바이트가 다르면 빠르게 중단되는 것이 합리적이지만 보안 상 끝까지 나쁜 소식을 전할 때까지 기다리게됩니다.
• 누군가는 복잡성이 낮은 알고리즘에 대해 특허를 받았으며 회사가 돈을 지불하는 것보다 더 높은 복잡성을 사용하는 것이 더 경제적입니다.
• 일부 알고리즘은 특정 상황에 잘 적응합니다. 예를 들어 삽입 정렬의 평균 복잡도는 O(n^2)퀵 정렬 또는 병합 정렬보다 나쁘지만 온라인 알고리즘 으로 대부분의 다른 알고리즘 만 효율적으로 작동 할 수있는 경우 사용자 입력으로 수신되는 값 목록을 효율적으로 정렬 할 수 있습니다 전체 값 목록에서.

답변