for-loop - 两个单独的 for 循环与两个嵌套的 for 循环的运行时间是多少？

Question

在这个例子中，我有两个独立的 for 循环。运行时间是 O(num1 + num2) 吗？

for(int i=0; i< num1 ; i++)     
{
   print i;
}

for(int i=0 ; i<num2 ; i++)
{
    print i;
}

对于这个例子，有一个嵌套的 for 循环。运行时间是否会是 O(num1*num2)，因为对于 0 到 num1 中的每个数字，您必须从 0 迭代到 num2？

 for(int i=0 ; i<num1 ; i++)
 {
     for(int j=0 ; j<num2 ; j++)
     {  
         print i;
     }
}

Answer 1

你可以更笼统。Big-O 表示法并不是要在给定实际参数的情况下找到准确的值。它是关于确定渐近运行时间。在这种情况下，我们可以将 num1 和 num2 替换为 n，其中 n 是从 0 开始的某个区间的上限。使用这种方法，我们会发现您的第一个示例的运行时间为 O(n)，而第二个示例的运行时间为示例将具有运行时 O(n^2)。第一个例子是线性时间，第二个例子是二次的。您很少需要比这更详细地对算法运行时进行分类。