如何计算添加判断条件后的如下Matlab代码的时间复杂度？

Matlab代码时间复杂度分析 #

你提供的代码完整结构如下：

for i=1:n
    for j=1:n
        if () % 判断是否执行后续内层循环
            for l=1:n 
                for m=1:n
                    ;
                end
            end
        end
    end
end

我们可以直接按不同场景给出时间复杂度结论：

• 最坏情况：if条件每次都判定为真，外层i、j两层循环共执行n²次，每次触发内层l、m两层n²次的循环，总操作量为n² * n² = n⁴，时间复杂度为O(n⁴)，这也是通常算法分析里默认给出的时间复杂度结果。
• 最好情况：if条件每次都判定为假，永远不会进入内层循环，仅执行外层n²次的循环遍历和条件判断，时间复杂度为O(n²)。
• 平均情况：需要结合if条件的触发概率计算，若每次if判定为真的概率为和n无关的常数值，平均时间复杂度仍为O(n⁴)；若if触发的总次数为和n无关的固定常数，平均时间复杂度则为O(n²)。

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