一、算法的基本特征

输入：算法具有零个或者多个输入
输出：算法至少一个或多个输出
有穷性：算法在执行有限的步骤后，会自动结束而不会无线循环，并且每个步骤在可接受的时间内完成
确定性：算法的每个步骤都具有去欸的那个的含义，不会出现二义性。算法在一定条件下，只有一条执行路径，相同的输入只有一种结果。算法的每个步骤都应该被精确定义而无歧义。
可行性：算法的每一步都是可行的。

二、算法设计的要求

2.1 正确性

算法的正确性是指至少应该具有输入、输出和加工处理无歧义性，能正确反映问题的需求，能够得到问题的正确答案。

算法程序没有语法错误
算法对于合法输入能够产生满足要求的输出
算法对于非法输入能够产生满足规格的说明
算法对于故意刁难的测试输入都有满足要求的输出结果

2.2 可读性

算法设计的目的之一是为了便于阅读、可理解和交流。

2.3 健壮性

当输入数据不合法时，算法也能做出相关处理，而不是产生异常、崩溃或者莫名其妙的结果

2.4 时间效率高和存储量低

三、算法效率的度量

算法采用的策略、方案
编译产生的代码质量
问题的输入规模
机器执行指令的速度
最优算法：随着n的增大，T（n）的增长速度最慢的为最优算法。

四、时间复杂度

4.1 大O阶

用常数1来取代运行时间中所有的加法常数
在修改后的运行次数函数中，只保留最高项
如果最高项目存在且不是1，则去除与这个项相乘的常数

4.2、时间复杂度分析示例

4.2.1 示例一

int i,j;
for(i = 0; i < n; i++){
	func(i)
}
void func(int count){
	printf("%d", count);
}

循环为N次，func为O(1)，所以为O(n)

4.2.2 示例二

void func(int count){
	int j;
	for(j = count; j < n; j++) {
		printf("%d", count);
	}
}

func随着count的增加而减少，所以时间复杂度为O（

n^2

$n^{2}$ ）

4.2.3 示例三

n++
func(n)
for(i = 0; i < n; i++) {
	func(i);
}
for(i = 0; i < n; i++) {
	for(j = i; j < n; j++) {
		printf("%d", j);
	}
}

4.3 常见的时间复杂度

例子	时间复杂度	术语
520	O(1)	常数阶
3n+4	O(n)	线性阶
3 $n^2 n2+4n+5$	O( $n^2 n2)$	平方阶
3 $\log_2n log2n+4$	O( $\log_2n log2n)$	对数阶
2n+3n $\log_2n log2n+14$	O(n $\log_2n log2n)$	nlogn阶
$n^3 n3+2 n 2 n^2 n2+4n+6$	O( $n^3 n3)$	立方阶
$2^n 2n$	O( $2^n 2n)$	指数阶

O(1) < O(

log

⁡

2

n

\log_2n

$lo g_{2} n$ ) < O(n) < O(n

log

⁡

2

n

\log_2n

$lo g_{2} n$ ) < O(

n

2

n^2

$n^{2}$ ) < O(

n

3

n^3

$n^{3}$ ) < O(

2

n

2^n

$2^{n}$ ) < O(n!) < O(

n

n

n^n

$n^{n}$ )

文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/137662.html