算法时间复杂度：最佳/最坏情况定义、冒泡排序示例及符号疑问

一、你的初始理解是否正确？ #

你的理解完全正确：

• 最佳情况时间复杂度：是算法终止所需执行的基本操作的最小次数的渐近估计，描述算法在最理想输入下的运行效率。
• 最坏情况时间复杂度：是算法终止所需执行的基本操作的最大次数的渐近估计，描述算法在最恶劣输入下的运行效率。

二、冒泡排序案例分析 #

你给出的带优化的C++冒泡排序代码如下：

int count = 0;
while(count<=n-1)
{
    bool check = false;
    int index = 0;
    while(index<=n-1)
    {
        if(array[index] > array[index + 1])
        {
            swap(array[index],array[index + 1]);
            check = true;
        }
        index++;
    }
    if(check != true)
    {break;}
    else{count++;}
}

你的分析完全准确：

• 最坏情况：当数组为降序排列时，每一轮外层循环都要执行完整的内层遍历和交换操作，总操作数为$\frac{n(n-1)}{2}$，忽略常数和低次项后，最坏情况时间复杂度为O(n²)。
• 最佳情况：当数组已经有序时，外层循环仅执行1次内层遍历（此时check保持false，直接跳出循环），总操作数为n级，所以最佳情况时间复杂度为Ω(n)。

三、空数组的特例疑问 #

当输入数组为空（n=0）时，算法不会进入任何循环，直接终止，基本操作次数是常数级（比如变量初始化的固定次数），此时最佳情况时间复杂度确实是Ω(1)。

但需要明确：我们讨论算法时间复杂度时，通常默认关注的是n≥1的常规输入场景，空数组属于输入规模的边界特例，和非空数组的最佳情况Ω(n)并不冲突——两者是不同输入规模下的结论。

四、复杂度符号的规范使用 #

关于符号的使用，这里明确行业通用的规范：

• 大O符号（O(·)）：表示渐近上界，约定俗成主要用于描述最坏情况时间复杂度，代表算法在最坏情况下的运行时间不会超过这个上界。
• 大Ω符号（Ω(·)）：表示渐近下界，约定俗成主要用于描述最佳情况时间复杂度，代表算法在最佳情况下的运行时间不会低于这个下界。
• 部分资料用O(·)表示最佳情况，本质是在描述“最佳情况下的运行时间上界”，但这属于不规范用法，容易造成混淆，不建议采用。
• 如果某个算法的最佳和最坏情况的渐近复杂度边界一致（比如二分查找，最佳和最坏都是O(logn)），可以用**Θ(·)**表示精确的渐近界。

内容的提问来源于stack exchange，提问作者Vishwas Sahai