-1

我在我的书以及互联网上的几个网站上搜索了高低，但我并不完全确定我的答案。

关于存在的反转数量，我需要给出 InsertionSort 和 FingerTreeSort（基于 RB-Trees）的渐近运行时。InsertionSort 运行时间为 O(n+INV)，FingerTreeSort 运行时间为 O(n+n*lg(INV/n+1)。我需要给出 INV = 0、n、n^1.5 和 n^2/ 的渐近运行时4.

我自己想出的是 InsertionSort 运行在：O(n)、O(n)、O(n^2) 和 O(n^2)

这个对吗？为什么不？（我特别不确定 INV = n 和 n^1.5）

对于 FingerTreeSort：O(n*lg(n))、O(n*lg(n))、O(n*lg(sqrt(n))) 和 O(n*lg(n^2))

我对 FingerTreeSort 中的所有内容都存有疑问，但我认为它们应该是这样的。如何找到正确的渐近运行时？例如对于 FingerTreeSort 和 n^1.5，我认为它会通过插入通用运行时给出 O(n+n*lg(n^1.5/n+1) 并简化： O(n+n*lg (sqrt(n)+1) 并且看到它是渐近的，我可以忽略 +1 和 +n 等较低的数字给我 O(n*lg(sqrt(n)))。这是正确的做法吗?

提前感谢那些回答这个问题的人。我非常喜欢它:)

附言。用java编写，这对问题并不重要。

4

1 回答 1

0

插入排序：
公式：O(n + inv)
inv = 0 : O(n)
inv = O(n) : O(n +n) = O(n)
inv = O(n^1.5) : O(n+ n^1.5) = O(n^1.5)
inv = (n^2)/4 : O(n + n^2) = O(n^2)

FingerTreeSort ：
公式（使用 OP 提供的公式）：O( n + n*(ln[(inv/n) +1 ] ) )
inv = 0 : O(n)
inv = O(n) : O(n + n*( ln[( O(n)/n ) + 1] ) ) = O(n + n*( ln[ O(1) +1] )) = O(n)
inv = O(n^1.5) : O(n + n*( ln[( O(n^1.5)/n ) + 1] ) ) = O(n + n*( ln[ c*(n^0.5) + 1] ) ) =
O( n + 0.5*n*ln(n)) = O(n*ln (n))
同样，对于 inv = O(n^2) : O(n*ln(n))

于 2012-05-30T09:48:17.993 回答