这个算法的时间复杂度是多少？

Question

下面code/algorithm的时间复杂度是多少？不应该是 O(a^2) 吗？我的老师说不，我需要更加努力地思考并专注于给定的限制。有人可以帮我解决这个问题吗？

function(int a, int b)
{
    for(i=0; i<a; i++)
    {
        for(j=0; j<a-i; j++)
        {
            k = a-i-j;
            if(8*i+4*j+2*k == b)
                return;
        }
    }
}

限制条件：

2a < b < 8a
b 总是偶数

Answer 1

代码会在找到i,j满足8i+4j+2(a-i-j)=b即6i+2j=b-2a时提前停止

j 循环从 0 到 a-i，因此对于 j 在范围内，有 b-2a = 6i+2j < 6i+2(a-i) = 4i+2a，得到 4i > b-4a。

所以我们需要执行 i 循环的 (b-4a)/4 次迭代才能找到 j。

我会跳过细节，但是可以检查 a>=6 总是有一个 j 使得当 i 是第一个至少为 (b-4a)/4 的值时循环退出（假定 b是偶数且 2a

计算迭代次数（并且始终将内部循环计算为 a 迭代而不是 a-i 迭代，这在最坏的情况下会产生 2 倍的误差），我们得到 a*max(1, b/4-a ) 迭代。

我在这里浏览了很多细节，但结果是复杂度为 Theta(a*max(1, b/4-a)).

Answer 2

在给定约束的情况下，假设您对最坏情况的复杂性感兴趣，它仍然是仍然 O(a²)。也许还缺少另一个约束条件？

Paul 的回答很好，并准确说明了复杂性。但是，要找到最坏情况的复杂性，您可以只展示最坏的情况。

等式8i+4j+2k = b改写为3i+j = b/2−a。因为 j < a−i，左侧至多为 3i+(a−i−1)，即 2i+a−1。因为 i < a，这最多是 2(a−1)+a−1，换句话说 3a−3。

取最大可能的 b：b = 8a−2（满足两个约束：b 是偶数且 2a < b < 8a）。等式的右侧变为 (8a-2)/2-a，换句话说，3a-1。这严格大于 3a−3，因此方程无解。在这种情况下，算法会尝试所有 (i,j)，这是二次方的。

这个算法的时间复杂度是多少？

What will be the time complexity of this algorithm?

algorithm

time-complexity