非递归算法分析实例分享

1 仅仅依赖于问题规模的时间复杂度

(1) 例1: 交换i和j的内容   
 

  t = i;
    i = j;
    j = t;

    以上三条语句的频度均为1，该算法段的执行时间是一个与问题规模n无关的常数。
因此，算法的的时间复杂度为常数阶，记作T(n)=O(1)。

    算法的时间复杂度是O(1)。


(2) 例2: 循环次数直接依赖规模n   
  

 x = 0; y = 0;
    for(k = 1; k <= n; k++)
       x++;
    for(i = 1; i <= n; i++)
       for(j = 1; j <= n; j++)
          y++;

    一般情况下，对计数循环语句只需考虑循环体语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。
因此，以上算法段中频度最大的语句是"y++"，其频度f(n) = n*n。

     算法的时间复杂度是O(n*n)。

     当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。

(3) 例3: 循环次数间接依赖规模n
  

 x = 1;
    for(i = 1; i <= n; i++)
       for(j = 1; j <= i; j++)
          for(k = 1; k <= j; k++)
              x++;

    该算法段中频度最大的语句是"x++"; 内层循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量
取值有关，而最外层循环的直接次数直接与n有关。因此可以从内层向外逐层计算语句"x++"的频度：

  
    f(n) = $(i:1~n)$(j:1~i)$(k:1~j) = $(i:1~n)$(j:1~i)j = $(i:1~n)(i*(i+1)/2) = (n(n+1)(2n+1)/6 + n(n+1)/2)/2
   
    算法的时间复杂度是O(n*n*n)。

2. 算法的时间复杂度还与输入实例的初始状态有关

   例： 在数组a[0, n-1]中查找给定的值k
  

 i = n - 1;
    while(i > 0 && a[i] != k)
	i--;
    return a[i];

    频度较高语句为"a[i] != k"。此算法的频度不仅与问题规模n有关，还与输入实例中的a的各元素取值及k值有关。

    <1> 若a中没有与k相等的元素，则语句的f(n) = n, 这是最坏情况；

    <2> 若a的最后一个元素等于k，则语句的f(n) = 1，这是最好情况。

    在求成功查找的平均情况时，一般假设查找每个元素的概率都是相同的，
    则平均时间复杂度为：(1+2+...+n)/2 = (n+1)/2 = O(n)