了解两个嵌套while循环的时间复杂度 [英] Understanding time complexity of two nested while loop

问题描述

下面的代码块来自一个函数，该函数查找达到用户给定数量所需的最小硬币数量.这里使用了两个队列和"和成本".

The following block of code is from a function that finds the minimum number of coins required to achieve a certain amount given by the user. Here two queue "sums" and "costs" are used.

while(Sums.front()<=TargetSum){
    int tempSum = Sums.front(); 
    Sums.pop();
    int tempCost = Costs.front(); 
    Costs.pop();

    for(int i=0;i<TypesOfCoins;i++)
    {
        Sums.push(coins[i]+tempSum);
        Costs.push(tempCost+1);
        if(Sums.back()==TargetSum)
        {
            cout<<"Sums:"; DisplayQueue(Sums);
            cout<<"Cost:"; DisplayQueue(Costs);
            return Costs.back();
        }
    }
}

据我所知，对于嵌套循环，复杂度是最内层循环迭代的次数，因此该循环的时间复杂度应为O(n ^ 2)，不是吗?

As far as I know, for nested loops times complexity is the numbers of times innermost loop iterates, so time complexity for this loop should be O(n^2), shouldn't it?

推荐答案

下面的两个示例即使 n 不同，也具有相同的复杂性.它们的复杂度或Big-O为O(InputData * 1)，即O(InputData):

The two examples below have the same complexity even that n is different. And their complexity, or Big-O, is O(InputData * 1) which is O(InputData):

int n = 10;
FuncA(int InputData)
{
    for(int i = 0; i < n; i++) // n is outer loop. 
    {
        for(int j = 0; j < InputData; j++) 
        {
            // .. do stuff
        }
    }
}

或

int n = 100000000;
FuncB(int InputData)
{
    for(int i = 0; i < InputData; i++)
    {
        for(int j = 0; j < n; j++) // n is inner loop
        {
            // .. do stuff
        }
    }
}

n 是一个常数，这意味着任何依赖 n 的循环都具有O(1)复杂度.

n is a constant, and that means any loop that depends on n has O(1) complexity.

InputData 不是常数，这意味着依赖于 InputData 的任何循环都具有O(InputData)复杂性.

InputData is not constant, and that means any loop that depends on InputData has O(InputData) complexity.

总复杂度=所有循环的复杂度=> O(InputData * 1)

Total Complexity = Complexity of all loops => O(InputData * 1)

请注意，这两个功能的"完成时间"不同(因为 n 较大，硬件速度等等.)但是"计算复杂度"是相同的:无论哪个循环是内部循环，还是常量有多大(本例中为 n ).

Note that "Time To Finish" for both functions is different (since n is bigger, hardware speed.. etc). But the "Computation Complexity" is the same: No matter which loop is the inner loop nor how big is the constant (n in this case).

一个好主意:如果您有问题并且知道如何解决，但这只需要10年的时间.那会复杂吗?

A nice idea: if you have a problem and you KNOW how to solve it, but it just requires 10 years of time. Would that be complex?

答案是否定的，并不复杂.这很简单，但是只需要时间.(在我的示例中， n 是处理某事物的时间，但是该过程没有复杂性，只是重复执行了固定的时间).

The answer is no, it is not complex. It is simple but just requires time. (n in my example is times to process something, but the process has no complexity, it is just repeated for a constant amount of time).

这篇关于了解两个嵌套while循环的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！