1
연습 테스트에서이 질문이 있는데 O (log n)보다 O (n * n)에서 코드가 더 빨리 실행될 지 확신 할 수 없습니다.언제 O (n * n)이 더 빠를 것인가? O (log n)?
A
답변
0
Big-O가 상한임을 기억하십시오. 작은 입력 크기에서 O (n^2) 알고리즘이 O (log n)보다 빠르게 실행될 수있는 상수 때문일 가능성이 큽니다. 대부분의 경우 n^2도 더 빠르게 실행될 수 있고 그 알고리즘은 많은 입력을해야만 많은 작업을 수행해야하기 때문에 n^2에서 실행될 수 있습니다.
6
큰 오 표기법은 상한을 제공합니다. 아니 더.
알고리즘 A가 O(n^2) 인 경우 정확히 n^2 단계가 필요할 수 있습니다.
알고리즘 B가 O(log n) 인 경우 정확히 10000 * log n 단계가 필요할 수 있습니다.
알고리즘 A는 작은 n에 대해 알고리즘 B보다 훨씬 빠릅니다.
0
기술적으로는 O(n*n) 알고리즘이 O(log n) 알고리즘보다 빠를 가능성이 높기 때문에 기술적 인 측면에서 필자의 이전 대답을 철회합니다. 자세한 내용은 그의 대답에 예수님과의 토론을보십시오. 아래 그래프는 시간 복잡도가 인 알고리즘이 정확히log n 인 알고리즘이 시간 복잡도가 인 알고리즘보다 정확히n*n 인 알고리즘보다 항상 빠릅니다.
+0
그들이 log2n을 의미하는지 확실하지 않습니다. log10n이 아닌가요? –
+2
알고리즘의 시간 복잡도에 대해 논의 할 때 우리는 기수 10이 아니라 기수 2를 항상 참조합니다. – ubiquibacon
+0
Big-O는 모든 상수와 요인을 앞의 용어에서 제거하므로 완전히 가능합니다. –
관련 문제
- 1. 큰 오 표기 O ((log n)^k) = O (log n)?
- 2. O (log n)은 항상 O (n)보다 빠릅니다.
- 3. 충돌 탐지를위한 O (n^log n) 알고리즘
- 4. ListBox.FindString 최악의 런타임은 무엇입니까? O (n), O (n log n), O (1)?
- 5. (log (n))^log (n) 및 n/log (n)은 더 빠릅니까?
- 6. O (n log n) 복잡도를 사용하여 Java HashMap을 값순으로 정렬합니다.
- 7. 왜 문자열 정렬 O (n log n)입니까?
- 8. O (n log n)보다 일반적이고 실용적인 정렬 알고리즘이 빠릅니까?
- 9. O (n log n) 시간에 특수 점 k를 찾는 알고리즘
- 10. 이진 검색 트리를 작성하는 이유는 O (N Log N)입니까?
- 11. T (n) = 2T (n/2) + O (n)
- 12. 왜이 함수/루프 O (log n)이 아니라 O (n)입니까?
- 13. LINQ의 .Where()가 O (N)보다 빠를 수 있습니까?
- 14. 점근 분석에서, - O (f (n) + g (n)) = O (max {f (n), g (n)})
- 15. O (2^n * n) 배낭 알고리즘
- 16. 개수 O (n)의 단어들
- 17. 방지 O (n)이 쿼리
- 18. O (fib n) 복잡도 알고리즘?
- 19. O (n)에서 작동하는 방법?
- 20. O (n) 정렬 알고리즘이 가능합니까?
- 21. O (log n) 시간에 배열에서 중복 요소 찾기
- 22. O (log (n)) 미만의 정렬 된 배열에서 검색 실행 시간
- 23. 쿼리를위한 O (log n) 복잡성을 가진 데이터 구조
- 24. O (log n) 복잡도에서 정렬 된 배열의 중앙값이란 무엇입니까?
- 25. Boost 풀 무료 효율성 O (n) 또는 O (1)
- 26. Big O Log 문제 해결
- 27. 배열 액세스 복잡성은 perl에서 O (1) 또는 O (n)입니까?
- 28. O (n) 시간 대괄호 패턴이있는 O (1) 부분 문자열 검색
- 29. memmove() O (n) 또는 O (1)을 고려해야합니까?
- 30. 이것은 무엇을 의미합니까? O (n) steps 및 O (1) space?
다양한 알고리즘의 세부 사항을 제외한 어떠한 입력 여기서 'N * n'은'n' 로그보다도 작은 존재하지 않는다. 그래프를 참조하십시오. – ubiquibacon
Big-O는 100000000 * logn + 큰 정수와 기본 n^2 알고리즘이 될 수 있으므로 가능한 모든 상수를 제거 할 수 있기 때문에 가능합니다. N^2 또한 상한값이다. 평균적으로 알고리즘은 loglogn 시간이나 그런 식으로 수행 할 수있다. –
알고리즘의 특성 (언급 한 제약 조건)이 아닌 입력 크기에 초점을 맞추고 있습니다. 실행 시간이 정확히'n * n '이고 실행 시간이 정확히'log n'인 두 개의 알고리즘이 있다면'n * n '이 더 빠를 수있는'n' 값은 없습니다 'log n'보다. – ubiquibacon