2
크기가 n 인 배열 A는 O (n) 역변환시 Θ (n)으로 정렬 될 수 있음을 입증하십시오.배열을 Θ (n) 복잡도로 정렬하십시오.
이 질문에 무엇이 요구되는지 정확히 알지 못합니다. 최선의 추측은 사전 정렬 된 입력에 삽입 정렬을 사용하고 정렬을 통해 Θ (n) 복잡성을 달성 할 수 있다는 것입니다. 이 질문이 내게 묻는 질문인가?
A
답변
3
관련 문제
- 1. 증명 Θ (n) + O (n^2) ≠ Θ (n^2)
- 2. klgk = Θ (n)이면 k = Θ (n/lgn)
- 3. 답은 무엇입니까? n! = Θ()?
- 4. 런타임 코드 (n) ∈ Θ (n^3/2)
- 5. 정렬을 정렬하여 n 개의 값 배열을 정렬하십시오.
- 6. T (n) = Θ 형식의 계산 복잡도
- 7. nC2가 Θ (n^2) 인 방법을 설명하십시오.
- 8. 이 알고리즘의 시간 복잡도는 Θ (n)입니까?
- 9. 해결 재발 T (N) = T (N/2) + Θ (1)
- 10. 동일한 작업에 대해 Θ (n) 시간 알고리즘에 대해 Θ (n log n) 시간 알고리즘을 사용할 수있는 이유
- 11. Perl 배열을 날짜순으로 정렬하십시오.
- 12. 배열을 먼저 정렬하십시오.
- 13. 어레이에 배열을 정렬하십시오.
- 14. 만약 T (n) = θ (n^2)가 T (n) = 0 (n)이라면?
- 15. 두 배열을 결합하여이 배열을 날짜순으로 정렬하십시오.
- 16. 주어진 시간 복잡도로 알고리즘 만들기
- 17. 푸시 된 배열을 mongodb에 정렬하십시오.
- 18. 차원을 따라 다차원 배열을 정렬하십시오.
- 19. C++, 고유성을 찾으려면 숫자 배열을 정렬하십시오.
- 20. 배열의 가장 작은 n/logn 요소를 정렬하십시오.
- 21. O (n log n)의 링크 목록을 O (1) 공간 복잡도로 정렬
- 22. 노드의 평균 깊이가 Θ (lg n) 인 n- 노드 이진 탐색 트리의 높이에 점근선 상한값을 부여하십시오.
- 23. 파일 배열을 만들고 루비의 날짜순으로 정렬하십시오.
- 24. PHP : 문자 뒤에 숫자가있는 배열을 정렬하십시오.
- 25. evens 전에 확률을 만들기 위해 배열을 정렬하십시오.
- 26. 구조체 배열을 제네릭 크기의 배열로 정렬하십시오.
- 27. PHP 배열을 부모 노드 아래의 자식으로 정렬하십시오.
- 28. 버블 문자 배열을 영문자 순으로 정렬하십시오.
- 29. PHP : 배열을 다른 배열의 문자 순서로 정렬하십시오.
- 30. PHP N 배열의 N 요소 배열을 나눕니다.
질문을 다시 말하면 좋겠습니까? –
"내가 생각하기에 미리 정렬 된 입력에 삽입 정렬을 사용하므로 O (n) 복잡도를 달성 할 수 있습니다." 음, 입력이 완전히 사전 정렬되지 않았습니다. (이 경우 역전은 일어나지 않을 것입니다.) 질문 당 O (n) 역변환이 있습니다. 그래서 그것은 5,4,7,6,10,9와 같은 것이 될 수 있습니다. 아래의 힌트를 사용하고 이와 같은 것을 정렬하는 것이 \ theta (n) 시간에 일어날 수 있음을 증명하십시오. – Shobit
@Shobit, 고마워! – dood