4

我试图弄清楚如何给出最坏情况的时间复杂度。我不确定我的分析。我读过嵌套for循环 big O is n^2；for这对于内部有循环的循环是否正确while？

// A is an array of real numbers.
// The size of A is n. i,j are of type int, key is
// of type real. 
Procedure IS(A)    
for j = 2 to length[A]     
{                
   key = A[ j ]               
   i = j-1   
   while i>0 and A[i]>key    
   {       
      A[i+1] = A[i]                         
      i=i-1                    
   }                
   A[i+1] = key      
}

到目前为止，我有： 

j=2 (+1 op)  

i>0 (+n ops)   
A[i] > key (+n ops)

so T(n) = 2n+1?

但我不确定我是否必须进入whileandfor循环来分析更坏的情况时间复杂度......

现在我必须证明它是紧束缚的，即 Big theta。

我读过嵌套for循环有 Big O of n^2. Big Theta 也是如此吗？如果不是，我将如何去寻找 Big Theta？！

**C1= C sub 1, C2= C sub 2, no= n naught 都是正实数的元素

为了找到T(n)我查看了的值j并查看了 while 循环执行了多少次：

values of J:   2, 3, 4, ... n  
Loop executes: 1, 2, 3, ... n

分析：
对 while 循环执行求和，并认识到它是(n(n+1))/2 I 将其分配为我的T(n)，并证明它由n^2. 那是n(n+1)/2= θ(n^2)

从头开始工作：

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2)for all n ≥ no

To make 0 ≤ C1(n) true, C1, no, can be any positive reals   
To make C1(n^2) ≤ (n(n+1))/2, C1 must be ≤ 1  
To make (n(n+1))/2 ≤ C2(n^2), C2 must be ≥ 1

公积金：

Find C1, C2, no є R+ such that 0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2(n^2) for all n ≥ no
Let C1= 1/2, C2= 1 and no = 1.

  1. 证明 0 ≤ C1(n^2) 为真 C1(n^2)= n^2/2
    n^2/2≥ no^2/2
    ⇒no^2/2≥ 0
    1/2 > 0
    因此 C1 (n^2) ≥ 0 被证明是正确的！

  2. 证明 C1(n^2) ≤ (n(n+1))/2 为真 C1(n^2) ≤ (n(n+1))/2
    n^2/2 ≤ (n(n+1 ))/2 n^2 ≤ n(n+1)
    n^2 ≤ n^2+n
    0 ≤ n

    我们知道这是真的，因为 n ≥ no = 1
    因此 C1(n^2) ≤ (n(n+1))/2 被证明是真的！

  3. 证明 (n(n+1))/2 ≤ C2(n^2) 为真 (n(n+1))/2 ≤ C2(n^2)
    (n+1)/2 ≤ C2(n)
    n+1 ≤ 2 C2(n)
    n+1 ≤ 2(n)
    1 ≤ 2n-n
    1 ≤ n(2-1) = n
    1≤ n
    另外，我们知道这是正确的，因为 n ≥ no = 1

    因此，根据 1、2 和 3，θ(n^2 )= (n(n+1))/2 为真，因为
    0 ≤ C1(n^2) ≤ (n(n+1))/2 ≤ C2( n^2) 对于所有 n ≥ no

告诉我你们在做什么...我正在努力理解这些材料，并希望大家提供意见！

4

3 回答 3

5

您似乎正在实现插入排序算法，维基百科声称它是 O(N 2 )。

通常，在处理 Big-O 时，您会根据变量 N 而不是常量 C 分解组件。在您的情况下，您需要做的就是查看循环。

您的两个循环是（更糟糕的情况）：

for j=2 to length[A]
    i=j-1
    while i > 0
        /*action*/
        i=i-1

外循环是 O(N)，因为它与元素的数量直接相关。

注意你的内循环如何依赖外循环的进度。这意味着（忽略一个问题）内部和外部循环的相关性如下：

j的内心
价值循环
----- -----
  2 1
  3 2
  4 3
  N N-1
----- -----
总计 (N-1)*N/2

所以遇到的总次数/*action*/是(N 2 - N)/2，也就是O(N 2 )。

于 2009-03-18T02:33:17.247 回答
2

查看嵌套循环的数量并不是获得解决方案的最佳方法。最好看一下代码中正在完成的“工作”，在重负载 N 下。例如，

for(int i = 0; i < a.size(); i++)
{
  for(int j = 0; j < a.size(); j++)
  {
    // Do stuff
    i++;
  }
}

是 O(N)。

一个函数 f 在 g 的 Big-Theta 中，如果它同时在 g 的 Big-Oh 和 g 的 Big-Omega 中。最坏的情况发生在数据 A 是单调递减函数时。然后，对于外循环的每次迭代，while 循环都会执行。如果每个语句贡献的时间值为 1，那么总时间将为 5*(1 + 2 + ... + n - 2) = 5*(n - 2)*(n - 1) / 2。这给出对数据的二次依赖。但是，如果数据 A 是单调递增的序列，则条件 A[i] > key 将始终失败。因此，外循环在恒定时间内执行 N - 3 次。那么 f 的最佳情况对数据具有线性相关性。对于一般情况，我们取 A 中的下一个数字，并在之前发生的排序中找到它的位置。平均而言，这个数字将在这个范围的中间，

于 2009-03-18T04:14:13.230 回答
0

Big O（基本上）关于循环中的元素将被查看多少次才能完成任务。

例如，O(n) 算法将只遍历每个元素一次。AO(1) 算法根本不需要遍历每个元素，因为它有一个索引，所以它会准确地知道要在数组中查找的位置。这方面的一个例子是数组或哈希表。

循环内部的循环是 O(n^2) 的原因是因为循环中的每个元素都必须对其自身迭代 ^2 次。更改循环的类型与它无关，因为它本质上是关于 # of 迭代。

有一些算法方法可以让您减少所需的迭代次数。其中一个例子是像Quicksort这样的“分而治之”算法，如果我没记错的话，它是 O(nlog(n))。

如果不更具体地了解您要完成的工作，很难为您的示例提出更好的替代方案。

于 2009-03-18T02:34:22.033 回答