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

我想弄清楚如何给出最坏的情况时间复杂度.我不确定我的分析.我已经读过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循环以分析更糟糕的案例时间复杂性......

现在我必须证明它是紧密绑定的,那就是Big theta.

我已经读过嵌套for循环有大O的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 我将此作为我的分配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.  

表明
0≤C1 (n ^ 2)为真C1(n ^ 2)= n ^ 2/2 n ^ 2 /2≥no^ 2/
2⇒no^ 2 /2≥01
/2> 0
因此C1 (n ^ 2)≥0被证明是真的!

表明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 +
n0≤n

我们知道这是正确的,因为n≥no= 1
因此C1(n ^ 2)≤(n(n + 1))/ 2被证明是正确的!

证明(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- n1≤n
(2-1)=
n1≤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

告诉我你们有什么东西......我正在努力理解这些材料,并希望你们都输入!

您似乎正在实现插入排序算法,维基百科称其为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     inner
value    loops
-----    -----
  2        1
  3        2
  4        3
  N       N-1
-----    -----
total    (N-1)*N/2

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