1.3.1定义概念算法是一个有限指令集在接受一些输入之后产生输出并一定在有限步骤之后终止。要求(1)算法的每一条指令必须有充分明确的目标不可以有歧义。(2)必须在计算机能处理的范围之内。(3)其描述应不依赖于任何一种计算集语言以及语言的实现手段。注意算法不是程序。程序可以无限运行但算法必须在有限步后终止。并且算法比程序“抽象”强调表现“做什么”忽略细节性的“怎么做”。优点使整体思路清晰形成模块化的风格。1.3.2算法复杂度(1)空间复杂度根据算法写成的程序在执行时占用储存单元的长度。这个长度往往与输入数据的规模n有关。(2)时间复杂度根据算法写成的程序在执行时花费时间的长度。这个长度往往与输入数据的规模n有关。分析一般算法时要观察下面两种复杂度·最坏情况复杂度T_worst(n)可以简单理解成输入最差时所需开销分析简单。·平均复杂度T_avg(n)所有输入加在一起的平均开销但“平均”很难定义分析困难。注意空间复杂度过高的算法肯导致使用的内存超限造成程序非正常中断时间复杂度过高的低效算法可能导致我们无法得到运算结果。1.3.3渐进表示法概念不精确笔记程序执行的步数只考虑n“充分大”时函数的“增长趋势”。数学符号(1)上界O(f(n))表示存在常数C0n_00,使得当n≥n_0时有T(n)≤C(f(n)).(2)下界Ω(g(n))表示存在常数C0,n_00,使得当n≥n_0时有T(n)≥C(f(n)).(3)紧界Θ(h(n))表示同时有T(n)O(f(n))和T(n)Ω(g(n))注意一个函数可以有很多不同的上界和下界通常取最小的上界和最大的下界。常见函数增长(复杂)程度O(1)O(logn)O(n)O(nlogn)O(n²)O(n³)O(2^n)O(n!)复杂度计算算法串联取复杂度大(速度慢)的。算法嵌套是复杂度相乘。如果T(n)是关于n的k阶多项式则T(n)Θ(n^k)一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度。若干次嵌套循环的时间复杂度等于各层循环次数的乘积再乘以循环体代码的复杂度。if-else结构的复杂度取决于if的条件判断复杂度和两个分支部分的复杂度总体复杂度取三者最大。