IAm*_*aja 9 algorithm big-o computer-science runtime
注意:请不要将其标记为作业!我不是学生,这不是作业.我是一名软件工程师,在我的旧数据结构和算法教科书上除尘,并试图记住我多年前学到的东西,而且我似乎无法在网上找到任何东西.
我记得一个特定的讲座,在我的教科书中得到了强化,算法界限(上,下和下)和案例(最佳,平均和最差)不是同一个.但对于我的生活,我不记得这两个概念是如何不同的.
对我来说,如果某些算法是O(n)最坏情况,那么它可以执行任何比某些线性函数更差的算法,例如f(n) = cn + k.由于我们在最坏的情况下保证这一点,在我看来它的上限也是线性的.
我知道我错了,我只是弄清楚为什么.
我是一个上下文学习者,所以如果有人可以提供一个有意义的例子,其中最坏情况不是上限,或者最佳情况不是下界,或者平均情况不是紧张的,那可能会通过我最快的.
感谢您对此的清晰度!
考虑一个quicksort的变体,它检查数组是否已经排序,如果没有,则使用第一个元素作为数据排序.
如果数组已经排序,最好的情况是O(n).这是最佳案例行为的上限,如果没有意义,这是有意义的.
随机输入的平均情况是O(n 3/2)和Ω(n).好吧,我作弊很轻微,因为它也是Theta(n log n),但是这个想法是边界并不总是紧张,当我描述平均情况界限时,这种缺乏紧张感可能会表现出来.
在最坏的情况下是西塔(N 2),如果该阵列被反向排序,这是因为子问题是如此不平衡(每次,我们枢转的最大元素,从而导致尺寸0的子问题和n - 1而不是大约π/ 2和关于n/2).这是对最坏情况的严格限制,并表明算法确实可能那么糟糕,但不会更糟.Quicksort也是O(n 3),但不是Theta(n 3),因为quicksort没有导致立方行为的输入族.