알고리즘 쿼리

2012-02-19 1 views 0 likes

이이라는 문제가 시간 복잡도로 묶여 있다는 것을 알고있는 경우 최악의 시간 복잡도를 갖는 알고리즘을 사용할 수 없다고 생각하면 정확합니까? O(n log n)? 문제의 시간 복잡도에 대한 하한이 Ω(n^2) 경우알고리즘 쿼리

2012-02-19 daryl

n^2의 하한을 의미합니까? –

nope, upper bound – daryl

상한이 O (n^2) 인 문제에 대한 예를들 수 있습니까? –

답변

후 즉,이 문제점을 해결하는 알고리즘은 적어도C*n^2 시간을 의미한다.

한편 을 사용하는 알고리즘은K*n*logn 시간입니다.

이 알고리즘은 nlogn보다 오래 실행될 수 없습니다. 필요한 것은 적어도 n^2 시간 실행되는 알고리즘입니다.

따라서; 이 알고리즘이이 문제를 해결하는 것은 불가능합니다. 당신이 올바른지.

2012-02-20 08:08:11