这是我的讲义中的一张幻灯片。我知道如果算法的最佳情况和最坏情况的复杂性相同,那么它就具有“每种情况”的复杂性。但是我不完全理解这个概念。我尝试在线进行研究,但无济于事。
谁能用其他例子更普遍地解释什么是每种情况的时间复杂度?
最佳答案
您发现下界 - 添加数组成员的渐近最小操作数是 O(n)。
你发现上界 - 添加数组成员的渐近最大操作数是 O(n)。
因此,所有其他情况都在 O(n) 和 O(n) 之间。所以它们也必须是 O(n)。
关于algorithm - Every-case 时间复杂度的概念,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32407829/