algorithm - 我如何找到时间复杂度 T(n) 并证明它是有界的(Big Theta)？

Question

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

// 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 循环来分析更坏情况下的时间复杂度...

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

我读到嵌套的 for 循环有 n^2 的大 O。 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我会将其指定为我的 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))/2n^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

告诉我你们的想法……我正在努力理解这些 Material ，希望你们能提供意见!

Answer 1

您似乎正在实现 insertion sort algorithm ，维基百科称其为 O(N²)。

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

你的两个循环是(最坏的情况):

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

外层循环复杂度为O(N)，因为它直接关系到元素个数。

请注意您的内循环如何取决于外循环的进度。这意味着(忽略差一问题)内循环和外循环的关系如下:

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

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