我记得有一个特定的讲座,在我的教材中也有强调,算法边界(上限、紧密和下限)和情况(最佳、平均和最差)并不相同。但是,我无论如何都想不起这两个概念的区别。
对我来说,如果某个算法在最坏情况下是O(n),那么它可以执行任何比某些线性函数更糟糕的函数,例如f(n)=cn+k。由于我们在最坏情况下保证了这一点,所以在我看来,它的上限也是线性的。
我知道我错了,我只是想不出为什么。
我是一位情境学习者,如果有人能提供一个有意义的例子,其中最坏情况不是上限,或最佳情况不是下限,或平均情况不是紧密边界,那可能是最快的方法。
感谢您对此的任何澄清!