Question

我查过书本的高度和低度和互联网上的几个网站一样但我只是不太清楚我的答案

I need to give asymptotic runtimes of InsertionSort and FingerTreeSort (based on RB-Trees), in regards to the number of inversions present. InsertionSort runs in O(n+INV) time and FingerTreeSort runs in O(n+n*lg(INV/n+1). I need to give asymptotic runtimes for INV = 0, n, n^1.5 and n^2/4.

我所想到的是,插入Sort 运行在:O(n),O(n),O(n),O(n),O(n)2和O(n)2

这是否正确?为什么不呢?(我特别不确定INV=n和n1.5)

对于FingerTreeSort: O(n*lg(n)、O(n*lg(n)、O(n)lg(sqrt(n))和O(n*lg(n)))

I m in doubt about all of the ones in FingerTreeSort, but these are how I think they should be. How do I find the right asymptotic runtime? For instance for FingerTreeSort and n^1.5, I m thinking that it would give O(n+n*lg(n^1.5/n+1) by plugging into the general runtime, and simplifying: O(n+n*lg(sqrt(n)+1) and seeing as it s asymptotic, I can disregard the lower figures such as +1 and +n giving me O(n*lg(sqrt(n))). Is this the correct way of doing it?

事先感谢回答这个问题的人。

p. 以java书写,与问题无关。

Answer 1

Insertion Sort :
Formula : 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 :
Formula (using the one supplied by 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))
Similarly,for inv = O(n^2) : O(n*ln(n))

友情链接