11
다항식 시간에 O (n Log n)입니까? 그렇다면 이유를 설명해 주시겠습니까?다항식 시간에 O (n Log n)입니까?
저는 수학적 증거에 관심이 있습니다. 그러나 강한 직감에 대해서도 감사 할 것입니다.
감사합니다.
A
답변
2
적어도 다항식 시간보다 나쁘지는 않습니다. 그래도 여전히 좋지는 않습니다. n < n log n < n * n.
2
다항식 (n)으로 상한하기 때문에입니다. 그래프를보고 거기에서 갈 수 있지만 그 이외의 수학적 증명을 공식화 할 수는 없습니다. P
편집 : 위키 백과 페이지에서 "알고리즘은 다항식 시간이라고합니다 그것의 실행 시간은 알고리즘에 대한 입력 크기의 다항식으로 상한값이된다. "
-1
예. n이 무한대로 갈수록 nlogn의 한계는 무엇입니까? 직관적으로, 큰 n, n >> logn에 대해 n이 지배하는 제품을 고려하면 nlogn ~ n을 분명히 다항식 시간으로 간주 할 수 있습니다. 더 엄격한 증거는 영감받은 Sandwich 정리를 사용하는 것입니다.
n^1 < nlogn < n^2.
따라서 nlogn은 다항식 시간 인 시퀀스로 묶여 있습니다 (아래).
+0
나는 그것이 1이라고 말하지 않았다. 우리가 페타 닉이라면 n이 무한대로 갈수록 n이 nlogn의 한계를 지배한다고 말할 수있다. 엄밀히 말하자면, 무한대로 움직이는 경향이 갈라진다. 두 개의 함수 f (n) * g (n)이있는 경우 제품이 lim f (n) * lim g (n) 인 경우이 한계는이 경우 무한대 * 무한대이며 정의되지 않습니다. – user1654183
+0
"nlogn의 n은 무한대로 이동합니다"는 "n은 n^1"입니다. 그 진술을 조금 더 설명해 주시겠습니까? – Teepeemm
+0
나는 벌써했다. 반복하려면 n이 무한대로 갈 때 n >> logn이됩니다. 따라서 n이 무한대로 갈수록 기본적으로 nlogn에 대한 logn의 기여도를 무시할 수 있습니다. 이것은 "엄격한"것이 아니라 직감을 요구했습니다 ... – user1654183
9
예, O (nlogn)는 다항식 시간입니다. http://mathworld.wolfram.com/PolynomialTime.html 가입일
: 주어진 입력에 대한 알고리즘을 수행하는 데 필요한 단계 수가 경우, 알고리즘이 알려져
다항식 시간 풀수 될 O 부가 아닌 정수 (N^m) 여기서 n은 입력의 의 복잡도입니다.
http://en.wikipedia.org/wiki/Big_O_notation에서 :
f는 지금 증명할
IFF O (g)는 그 N 로그 N은 O (N^m)의 일부이며 m은 n log n이 다항식 시간임을 의미합니다.
실제로 m = 2를 사용하십시오. (이것은 n log n이 O (n^2)임을 증명할 것임을 의미한다)
증명을 위해 k = 2를 취한다. (더 작을 수는 있지만 반드시 그럴 필요는 없습니다.) 큰 n에 대해 다음과 같은 n_0이 있습니다.
n_0의 *의 F (n)이 < = g (N) * K
테이크 n_0 = 1 (이 충분) 참조 이제 쉽게
N 로그 N < = 2N 그 * N
로그 < N = 2N
N> 0 (가정)
클릭이 점에 대해 확실하지 않으면 10 점.
이 증명은 라텍스 수학 모드에서 훨씬 더 좋을 수 있지만 stackoverflow가이를 지원한다고 생각하지 않습니다.
+1
'log n <= 2n'을 증명하는 것은 어떨까요? :) – Inspired
+0
1. 그'n_0'는 없어야합니다. 2.'logn <2n'을 증명하기 위해'logn
관련 문제
- 1. log (n!) = O ((log (n))^2)입니까?
- 2. O (n log n) 시간에 특수 점 k를 찾는 알고리즘
- 3. 큰 오 표기 O ((log n)^k) = O (log n)?
- 4. n/(log (n))은 다항식 시간으로 간주됩니까?
- 5. O (log n) 시간에 배열에서 중복 요소 찾기
- 6. O (log (n)) 시간에 목록을 검색하는 알고리즘을 만들 수 있습니까?
- 7. 그래프 검색에 O (log (N) (N + M))
- 8. 충돌 탐지를위한 O (n^log n) 알고리즘
- 9. Codility 's Peaks에 대한 O (N * log (log (N))) 알고리즘?
- 10. O (log n)은 항상 O (n)보다 빠릅니다.
- 11. O (log (n))과 O (n)의 차이점은 무엇입니까?
- 12. 시간 복잡도 O (N) 또는 O (Log N)입니까?
- 13. Brainstorm : log (n) 시간에 x/y를 계산하려면
- 14. log n 시간에 확률 론적 순위를 찾으십시오.
- 15. 병합 정렬의 최악의 경우가 여전히 n log n입니까?
- 16. Big O, n * logn (n) 및 n * log (n^2)
- 17. ListBox.FindString 최악의 런타임은 무엇입니까? O (n), O (n log n), O (1)?
- 18. O (log n) quicksort 복잡성, 가능합니까?
- 19. 순차 검색은 o (n^2) 시간이 걸립니다. O (1) 또는 O (log n)이 되길 원합니다.
- 20. 큰 O 표기법으로 O (log n)을 계산하는 방법은 무엇입니까?
- 21. (log (n))^log (n) 및 n/log (n)은 더 빠릅니까?
- 22. c> 0 인 경우 Log (n) = O (n)? 왜 그렇지 않은지 잘 모르겠다 O (log n)
- 23. O (n log n) 복잡도를 사용하여 Java HashMap을 값순으로 정렬합니다.
- 24. 왜 문자열 정렬 O (n log n)입니까?
- 25. 시간 복잡도가 O (sqrt (n) * log (n)) 인 알고리즘이 있습니까?
- 26. O (n log n)보다 일반적이고 실용적인 정렬 알고리즘이 빠릅니까?
- 27. 머지 정렬을 O (n log n)이되도록하는 데 문제가 있습니다
- 28. 이진 검색 트리를 작성하는 이유는 O (N Log N)입니까?
- 29. O (n^2 * log (n))과 O (n^3) 어느 것이 더 큽니까?
- 30. 언제 O (n * n)이 더 빠를 것인가? O (log n)?
이 답변은 단순한 오류입니다. http://en.wikipedia.org/wiki/Big_O_notation, http://en.wikipedia.org/wiki/Time_complexity 및 http://mathworld.wolfram.com/PolynomialTime.html –
자세히 설명해주세요. 여기 정확히 틀린거야? (컴퓨터 과학에서 Big-O는 종종 Big-Theta의 의미로 사용됩니다.) – Inspired
O (n^2)는 여전히 다항식 시간입니다. n