"磨棱角，褪优越，沉下心"
"不止于心动，更付诸于行动，执行力！“
引言
本章接着前面的绪论记录，本章主要记录算法相关的基本概念。在这里只记录一些核心需要掌握的东西了。
算法与算法分析
算法定义
算法是对特定问题求解方法和步骤的一种描述，它是指令的有限序列。其中每个指令表示一个或多个操作。算法就是解决问题的方法和步骤。
算法的特性
- （1）有穷性
一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 - （2）确定性
算法中的每一条指令必须有确切的含义，没有二义性，在任何条件下，只有唯一的一条执行路径，即对于相同的输入只能得到相同的输出。 - （3）可行性
算法是可执行的，算法描述的操作可以通过已经实现的基本操作执行有限次来实现。 - （4）输入
一个算法有零个或多个输入。 - （5）输出
一个算法有一个或多个输出。
算法设计的要求
- （1）正确性（Correctness）
正确性：算法满足问题要求，能正确解决问题。
算法转化为程序后要注意：
①不含语法错误。
②对于几组输入数据能够得到满足要求的结果。
③对于精心选择的、典型、苛刻且带有刁难性的几组输入数据能够得到满足要求的结果。
④对于一切合法的输入数据都能得到满足要求的结果。
以第三层意义上的正确性作为衡量一个算法是否合格的标准。 - （2）可读性（Readability）
可读性：
①算法应该易于人的理解。
②晦涩难懂的算法易于隐藏较多错误而难以调试。 - （3）健壮性（Robustness）（鲁棒性）
健壮性：
①指当输入非法数据时，算法恰当的做出反应或进行相应处理，而不是产生莫名其妙的输出结果。
②处理出错的方法，不应是中断程序的执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。 - （4）高效性（Efficiency）
高效性：要求花费尽量少的时间和尽量低的存储需求。
算法分析与评估
对于同一个问题，可能有许多种不同的方法，也就是有许多种算法，需要衡量评估哪种方法好，择优问题。
算法效率
算法效率以下两个方面来考虑：
- 时间效率：指的是算法所耗费的时间。
- 空间效率：指的是算法执行过程中所耗费的存储空间。
时间效率和空间效率有时候是矛盾的。
算法时间效率的度量
算法时间效率可以用依据该算法编制的程序在计算机上执行所消耗的时间来度量。
（1）度量方法
- 事后统计：将算法实现，测算其时间和空间开销。
缺点：编写程序实现算法将花费较多的时间和精力；实验结果依赖于计算机的软硬件等环境因素，掩盖算法本身的优劣。 - 事前分析：对算法所消耗资源的一种估算方法。
事前分析方法：
方法：算法运行时间=一个简单操作所需的时间*简单操作次数。
算法运行时间=Σ每条语句的执行次数*该语句执行一次所需的时间。
每条语句的执行次数又称为语句频度
算法运行时间=Σ每条语句频度*该语句执行一次所需的时间
实际评估算法时间效率，并不需要很明确知道每条语句执行的时间，这里运用高数上面的极限、等价相关的思想，直接简化只用执行的次数来衡量算法的时间效率了。
下面是资料的相关描述：
每条语句执行一次所需的时间，一般是随机器而异的。取决于机器的指令性能、速度以及编译的代码质量。是由机器本身软硬件环境决定的，它与算法无关。所以，我们可假设执行每条语句所需的时间均为单位时间。此时对算法的运行时间的讨论就可转化为讨论该算法中所有语句的执行次数，即频度之和了。这就可以独立于不同机器的软硬件环境来分析算法的时间性能了。
例子：
两个n*n矩阵相乘的算法
//两个n*n矩阵相乘的算法
for(i = 1; i <= n; i++){//n+1次
for(j = 1; j <= n; j++){//n(n+1)次
c[i][j] = 0;//n*n次
for(k = 0; k < n; k++){//n*n*(n+1)次
c[i][j] = c[i][j] + a[i][k] * b[k][j];//n*n*n次
}
}
}
时间复杂度
背景：
若有某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)= O(f(n))，称O(f(n))为算法的渐进时间复杂度（O是数量级的符号)，简称时间复杂度。
对于求解矩阵相乘问题，算法耗费时间: T(n)= 2n3+ 3n2+2n＋1。
上面例子中T(n)和n3具同阶或同数是级，引入大"O记号，则T(n）可记作:T(n)=0(n3)。
算法中基本语句重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作:
T(n) = O(f(n))
基本语句是算法中重复执行次数和算法的执行时间成正比的语句；对算法运行时间的贡献最大；执行次数最多。
n越大算法的执行时间越长（排序：n为记录数；矩阵：n为矩阵的阶数；多项式：n为多项式的项数；集合：n为元素个数；树：n为树的结点个数；图：n为图的顶点数或边数）。
计算时间复杂度
一般情况下，不必计算所有操作的执行次数，而只考虑算法中基本操作执行的次数，它是问题规模n的某个函数，
忽略低次项和高次项的系数，体现增长率的含义
方法步骤
- ①找出语句频度最大的那条语句作为基本语句。（执行次数最多的语句）
- ②计算基本语句的频度的得到问题规模n的某个函数f(n)。（最难最关键）
- ③取其数量级用符号“O”表示。
例子：（一些例子涉及到高数的级数了，很陌生了，头疼，先暂时忽略）
void exam(float x[][], int m, int n)
{
float sum[];
for(int i = 0; i < m; i++) //执行m+1次
{
sum[i] = 0.0;
for(int j = 0; j < n; j++)//执行（n+1）*m次
{
sum[i] += x[i][j];//嵌套最深层语句 执行m*n次
}
}
for(i = 0; i < m; i++)
{
cout << i << ":" << sum[i] << endl;
}
}
f(n)= m*n;
时间复杂度表示为：T（n）= O(m*n);
for(i = 1; i <= n; i++){
for(j = 1; j <= i; j++){
for(k = 1; k <= j; k++){
x = x + 1;
}
}
}
下面这个是考研的真题：
//分析以下程序段的时间复杂度
i = 1;//语句1
while(i <= n){
i = i * 2;//语句2
}
复杂度比较
小结
基本到这里就结束了绪论的学习，大概记录这些了！
参考资料：
青岛大学.王卓.数据结构与算法
《数据结构 C语言版》.严蔚敏
欢迎关注本人微信公众号：那个混子
记录自己学习的过程，分享乐趣、技术、想法、感悟、情感！
单片机类嵌入式交流学习可加企鹅群：120653336
网友评论