神刀安全网

算法的时间复杂度推导方法

算法的时间复杂度推导方法

语句频度

语句频度是指语句的重复执行次数。

推导大O阶方法

方法
  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最高阶项。
  3. 如果最高阶项存在且不是1,则去除与这个项相乘的乘数。
常数阶举例运用

右侧注释中的 num 表示语句执行的次数。

int sum = 0, n = 100;       /* num = 1 */ sum = (n+1) * n / 2;        /* num = 1 */ printf("%d", sum);            /* num = 1 */

这段代码的运行次数函数是 f(n) = 1 + 1 + 1 ,根据“推导大O阶方法”中的第一条规则,把
1 + 1 + 11 替换,运行次数函数变成了 f(n) = 1。该函数只有常数项,只需使用规
则1就可以推导出它即这段代码的时间复杂度是 O(1)

假如 sum = (n+1) * n / 2 执行3次,将上面的代码修改为:

int sum = 0, n = 100;       /* num = 1 */ sum = (n+1) * n / 2;        /* num = 1 */ sum = (n+1) * n / 2;        /* num = 1 */ sum = (n+1) * n / 2;        /* num = 1 */ printf("%d", sum);            /* num = 1 */

这段代码的运行次数函数是 f(n) = 1 + 1 + 1 + 1 + 1 。 按照推导大O阶第一条规则,用1取代
所有的加法常数,这段代码的运行次数函数是 f(n) = 1。这段代码的时间复杂度依然是 f(n) = O(1)

所有这类代码的时间复杂度都是 O(1)O(1)叫做常数阶。不存在 O(2)O(9) 这类写法。

线性阶举例运用

code-3

int i; for(i = 0; i < n; i++){     // 时间复杂度为O(1)的代码 }

code-3的运行次数函数是 f(n) = n * 1。加法常数为0个,跳过规则一。变量n的最高阶是 n * 1,无
其他项,跳过规则二。n * 1中的系数本来就是1,也可以直接跳过规则三,得到code-3的时间复杂度是
f(n) = O(n)

code-4

int i; for(i = 0; i < n; i++){     // 时间复杂度为O(1)的代码 }  int j; for(j = 0; j < m; j++){     // 时间复杂度为O(1)的代码 }

code-4的运行次数函数是f(n) = n * 1 + m * 1。直接跳过规则一。n * 1 + m * 1有两个变量,
但次数都是1,任何一项 n * 1m * 1 都可视为最高价,根据推导规则二“保留最高阶”,得出
运行次数函数是f(n) = n * 1f(n) = m * 1。最后根据规则三,得出code-4的时间复杂度是
f(n) = O(n)

对数阶举例运用

code-5

int count = 1; while(count < n){     count = count * 2;     //其他时间复杂度为O(1)的代码  }

code-5似乎不能用前面的推导大O阶方法来分析时间复杂度,我从《数据结构与算法分析》P21找到了分析
“运行时间中的对数”的一般法则。这个一般法则是:

如果一个算法用常数时间(O(1)将问题的大小削减为其一部分(通常是1/2),那么该算法就是 O(log N)
另一方面,如果使用常数时间只是把问题减少一个常数(如将问题减少1),那么这种算法就是 O(N)

code-5中,假设 n = 8 ,初始化时,while(count < n) 需要运行8次。经过一次循环后,count变为2,
循环需要运行4次,变为原来的一半。根据那条一般法则,判断 code-5 的时间复杂度是 O(log N)

code-5修改为code-6

int count = 1; while(count < n){     count = count + 2;     //其他时间复杂度为O(1)的代码  }

code-6每次执行循环后,会把问题减少2个常数,时间复杂度应为 O(N)

若将code-6中的count = count + 2改为code = count - 2,时间复杂度仍然是 O(N)。但我有点理解不了。

平方价举例运用

code-7

int i, j;    /*1*/ for(i = 0; i < n; i++){    /*2*/     for(j = 0; j < n; j++){    /*3*/         //时间复杂度为O(1)的代码    /*4*/     }    /*5*/ }    /*6*/

code-7中第二个循环体的时间复杂度是O(N)。第一个循环体将第二个循环体再执行N次,时间复杂度变为O(N2)
如果将第二个循环体中的n改为m,那么code-7的时间复杂度就是O(N*M)。注意,O(N*M)O(N2)都叫做
平方阶,二者实质相同。

多层循环体的时间复杂度就是每层循环体的运行次数相乘。

code-8

int i, j; for(i = 0; i < n; i++){     for(j = i; j < n; j++){         //时间复杂度为O(1)的代码     } }

code-8运行次数是(n+1)*n*n/2。只保留最高阶并且去掉它的系数,时间复杂度是O(N2)。有些地方理解不了。

code-9

void function(int count){      int j;      for(j = count; j < n; j++){          printf("%s", "hello,world");      } }  n++;        /* num = 1 */  function(n);    /* num = n */  int i,j;    /* num = 1 */  for(i = 0; i < n; i++){        /* num = n*n */      function(i);  }  for(i = 0; i < n; i++){            /* num = (n+1)*n/2 */      for(j = i; j < n; j++){          printf("%s", "hi");      } }

code-9的时间复杂度是多少呢?

首先将每行代码的执行次数标出来。

code-9的执行次数(首先忽略掉常数项)是n + n*n + (n+1)*n/2,计算结果为1.5*n*n + 2*n
只保留最高阶1.5*n*n,最后将系数变为1,执行次数为n*n,时间复杂度为O(N2)

这种方法有不确定性的因素存在,或者说,在计算执行次数的时候,使用了互相矛盾的方法。

重新思考之后,发现并不存在矛盾,而是《大话数据结构》中推导时间复杂度的方法有小缺陷。这个推导
本身就是一种粗略估计,为何在推导过程中有时又在进行精确计算呢?以code-8为例,该书使用了精确
的计算方法。若全部都坚持使用粗略估计计算,那么计算过程是这样的:code-8中第二个循环体的运行
次数是N,或者抽象为“一个变量”,第一个循环体的运行次数也是N或M,也抽象为“一个变量”,整体的运行
次数为两个变量相乘,即时间复杂度为O(N2)。这种粗略估计计算方法,建立的基础是:影响循环执行次数
的变量只有那个与循环终止条件相关的变量,与起始变量无关。

这种方法,又不能适用于对数阶的时间复杂度推导。或许,对数阶中的循环,本来就是一种特殊情况,不能
采用普通循环的推导方法。此处存疑。*

常见的时间复杂度

直接摘抄《大话数据结构》中的有关部分。
>

算法的时间复杂度推导方法
常见的时间复杂度

>

理解不了这些时间复杂度所耗时间的顺序,应该如何比较它们所耗时间?

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 算法的时间复杂度推导方法

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址