假设我有一个例程,扫描n个项目的整个列表3次,根据大小进行排序,然后bsearches排序列表n次.扫描是O(n)时间,我将调用O(n log(n)),n次bsearch是O(n log(n)).如果我们将所有3加在一起,它是否只是给我们3的最坏情况 - n log(n)值或者语义是否允许增加时间？
很确定,现在我输入的答案是n log(n),但我现在也可以确认我输入了:)
Ray*_*oal 10
总和确实是Big-O三者中最差的.
原因是你的函数的时间复杂度是
(n) => 3n + nlogn + nlogn
是的
(n) => 3n + 2nlogn
此函数以3nlogn 为界,因此它在O(n log n)中.
你可以选择任何常数.我恰巧选择3因为它是一个很好的渐近上界.