嵌套 for 循环的复杂性

Question

我想找出下面代码的复杂度。 我使用此代码通过排序查找数组中第二高的元素。

for(i=0;i<2;i++)
{
   for(j=0;j<n;j++)
   {
     //some code
   }
}

复杂度是 O(2n) 还是 O(n²)？

Answer 1

这是一个非常广泛的话题。我只是尽我的努力把它带给你。剩下的你可以引用一些好书。我的推荐Coreman .

复杂性:

for循环的基本结构是

for(initialization;condition;updation)

在更新中，我们正在更新值，所以基本上我们正在迭代循环直到条件。

所以就像

n*(n+1)/2

在两个 for 循环情况下基本上是 O(n^2)。

复杂性估计:

有时获得算法复杂度的公式并不容易。在这种情况下，可以通过实验来估计它。计数变量可以添加到程序中，在执行某些关键操作时递增并打印最终总数。运行时间也可以通过秒表来测量，或者更好地通过调用例程来打印计算机系统的时钟。复杂性可以通过检查这些度量如何随问题大小而变化来推断。

通过对多次执行(可能在循环中)进行计时，并将所用的总时间除以该次数，可以提高对程序或操作进行计时的准确性。分时计算机由许多人同时使用。程序所花费的时间取决于系统负载。因此，在共享计算机上完成的任何计时都必须基于专用于所研究的特定程序的中央处理器时间，而不是基于耗时。

检查序列中相邻项之间的差异可以表明定义该序列的基础函数的形式。线性函数 T(n)=a*n+b T(n) 之间产生恒定差异和T(n-1) :

D1(n) = T(n)-T(n-1) = a*n+b-a*(n-1)-b = a

二次函数 T(n)=a*n2+b*n+c产生线性一阶差分:

D1(n) = T(n)-T(n-1) = a*n2+b*n+c-a*(n-1)2-b*(n-1)-c = 2a*n-a+b

这会产生恒定的二阶差分 D2(n) = D1(n)-D1(n-1) 。一般来说，d 次多项式由常数 dth-order 揭示差异。