-4

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

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

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

4

4 回答 4

2

这是一个非常广泛的话题。我只是在努力把它带给你。休息你参考一些好书吧。我在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差揭示。

于 2013-08-21T06:29:23.813 回答
1

了解解决方案的最好方法是画一张表格：

Iteration |   i    |   j
----------+--------+-------
    0     |   0    |   0
    0     |   0    |   1
    0     |   0    |   2
    0     |  ...   |  ... 
    0     |  ...   |  ...
    0     |  ...   | n - 1
    1     |   1    |   0
    1     |   1    |   1
    1     |  ...   |  ... 
    1     |  ...   |  ...
    1     |  ...   | n - 1

执行多少次？这就是答案。
如果你想有一个直觉，你应该选择一些n，运行一个例子。然后选择另一个n，看看你得到了什么，最后你会得出答案是什么。

于 2013-08-21T06:16:59.947 回答
0

Big Oh 表示法给出了数量级估计，常数的差异实际上不会影响算法的大小，因此 O(2n) = 2O(n) = (n)。

类似于 1000 >> 10 = 5。也就是说，1000 比 10 大得多，并且它比 5 和 10 一样“大”，即使 10 是 5 的两倍。

于 2013-08-21T06:56:20.527 回答
0

如果“某些代码”执行 o(1)，则此代码的复杂度为 O(2n)

那是因为内部代码的复杂度为 o(n)，我们执行此循环 2 次。然后是 O(2n)

于 2013-08-21T06:09:52.627 回答