DS第二篇附：预定义常量（C++描述）、算法时间复杂度分析举例

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了DS第二篇附：预定义常量（C++描述）、算法时间复杂度分析举例，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1591字，纯文字阅读大概需要3分钟。

内容图文

预定义常量

• 在接下来的数据结构描述中要用到：
  这里是C++描述的预定义
  // 函数结果状态
#define OK 1
#define ERROR 0
#define OVERFLOW -2
//Status 是函数返回值类型，值为返回的状态
typedef int Status
//这里Status其实就是int
• Python描述的预定义
  …

---

算法时间复杂度分析举例(非递归算法)

书中定理1.1：
若 f(n) = a_mn^m + a_m-1n^m-1+…+a₁n+a₀ ，是一个m次多项式
那么，T(n) = O(n^m)
也就是说，忽略低次幂项、高次幂项的系数

常量阶

{x++;s=0;}

for (i=0;i<l0000; i++) {
	x++; 
	s=0;
	}

两条语句频度以及循环体频度，均为1
算法的执行时间是一个与问题规模n无关的常数，
T(n)= O(1), 常量阶。
`
需要注意的是如果算法中语句频度是某个常数。
即使这个常数再大，算法的时间复杂度都是O(1)。

线性阶

for (i=0; i<n; i++) {
	x++; 
	s=0;
	} 

循环体内两条基本语句的频度均为f(n)=n,
T(n)= O(n), 线性阶。

平方阶（&&/and）立方阶 k次方阶

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

对循环语句只需考虑循环体中语句的执行次数，
以上程序段中频度最大的语句是(6)y++;,频度为f(n)=n²,
T(n)= O(n²)，平方阶。

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

该程序段中频度最大的语句是(5)x++;
然后书中有这样一张图：

用到了等差数列前n项和公式、以及 （前n项）平方和公式

这是一个数学问题。可以参考一下这位网友图文并茂的解释
或者我大概说一下：
来，深呼吸一口气，试想：
当i=1，（5）执行1次
当i=2，（5）执行1+2次
当i=3，（5）执行1+2+3次
…
对于i=n，（5）执行(1+n)n/2次
于是只要把上边的执行次数全部加起来，就是问题规模了
也就是计算：

T(n)= O(n³) , 立方阶。

那么k次方阶，也就是二、三次方阶的扩展

对数阶

for (i=l; i<=n; i=i*2) {
	x++;
	s=0;
	} 

设循环体内两条基本语句的频度为f(n),则有
2^f(n)<=n, 两边同时对2取对数，得
f(n)<=log₂n,
T(n) = O(log₂n), 对数阶。

内容总结

以上是互联网集市为您收集整理的DS第二篇附：预定义常量（C++描述）、算法时间复杂度分析举例全部内容，希望文章能够帮你解决DS第二篇附：预定义常量（C++描述）、算法时间复杂度分析举例所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---