我怎么找到时间的复杂性T(n)，并表明它是紧密地界(大Theta)?

Question

我试图找出如何得到最糟糕的情况时的复杂性。我不知道我的分析。我已经阅读嵌套 for 循环大O是 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?  

但我不确定如果我必须进去的 while 和 for 循环到分析的一个糟糕的情况下时间的复杂程度...

现在我要证明它是紧密结合，这是大西塔。

我读过这套 for 循环已经大O n^2.这也适用于大西塔?如果不是我怎么会去找到大西塔?!

**C1=C子1,C2=C子2，并没有=n化为乌有的所有因素的正实际数字

找到的 T(n) 我看着这个的价值 j 看着如何许多次，而循环执行：

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

分析：
采取的总和，同时循环处决，并认识到它 (n(n+1))/2 我将这作为我的 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  

PF:

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号≥没有^2/2号
   ⇒没有^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+1)
   n^2≤n^2+n
   0≤n

   这我们知道是真的因为n≥没有=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≤2C2(n)
   n+1≤2(n)
   1≤2n-n
   1≤n(2-1所)=n
   1≤n
   此外，我们知道这是真实的，因为n≥没有=1

   因此，由1、2和3，θ(n^2)=(n(n+1))/2是真的因为
   0≤C1(n^2)≤(n(n+1))/2≤C2(n^2)对所有n≥没有

告诉我你的事情的家伙...我试着去理解这种材料，并想y'alls输入!

Answer 1

你似乎是执行《 插入排序的算法, ，维基百科的要求是O(N²).

一般来说，你打破分基于关闭你的变N而不是你的恒C在处理大-O.在你的情况下，所有你需要做的是看看循环。

你的两个循环的是(更糟糕的情况下):

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

外循环是O(N)，因为它直接涉及到的数量元素。

注意你的内环路上取决于进展的外循环。这意味着(忽略掉的一个问题)的内外环路是相关的如下：

 j's     inner
value    loops
-----    -----
  2        1
  3        2
  4        3
  N       N-1
-----    -----
total    (N-1)*N/2

因此总的次数 /*action*/ 遇到的是(N² -N)/2，这是O(N²).

Answer 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和大-欧米茄克。最糟糕的情况发生时的数据，一是减少单调的功能。然后，每一个迭代的外循环，同时循环执行。如果每个发言做出贡献的时间价值1，那么总的时间将5*(1+2+...+n-2)=5*(n-2)*(n-1)/2.这给二次依赖的数据。然而，如果数据是单调增加的顺序，条件A[i]>的关键将总是失败。此外循环执行在固定的时间,N-3倍。最好的情况下，f然后有一个线性依赖的数据。平均情况下，我们采取下一个号码，找到其地方在排序具有先前发生的。平均而言，这一数字将在这个范围内，这意味着内在的循环将运行的一半，经常作为在最坏的情况下，给予二次依赖的数据。

Answer 3

大O(基本的)关于如何许多次的元素在你的循环将看着为了完成任务。

例如，一个O(n)的算法将通过循环访问的每一个元素只有一次。O(1)的算法将没有通过循环访问的每一个元素，它将确切地知道在哪里阵列中来看，因为它有一个指数。这样的一个例子是一系列或哈希表。

原因一个循环内部的一个循环O(n^2)是因为中的每个元素的循环已被迭代过本身^2倍。改变类型的循环已经没有它，因为它是有关的迭代。

有办法的算法，这将能让你的数量减少的迭代的需要。一个例子，这些都是"除与征服"算法像 快速排序, 如果我记忆正确的是O(时间复杂(n))。

它是艰难的，来了一个更好的选择你不知道更具体地说什么，你在试图完成的任务。