C语言/C++算法基本概念

分享编程技能、互联网技术、生活感悟、打造干货分享平台，将总结的技术、心得、经验分享给大家，这里不只限于技术！还有职场心得、生活感悟、以及面经。

C语言/C加加算法基本概念

1. 算法是什么

算法：顾名思义，一种计算的方法，在程序设计上，就表现为一组指令序列。

为了使得算法有意义，还规定算法必须是有限的和确定的，也就是说算法的执行时间有限、执行的过程是确定的。

比如我们写了代码

int a = 10; //a，b为输入数据

int b = 20;

int c = a+b; //c为输出数据，算法为加法运算

小编推荐一个学C语言/C++的学习裙【 二六三，六八八，二七六 】，无论你是大牛还是小白，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！

这其实就是一个算法的具体实现（程序就是算法的具体实现，但不是所有程序都能认为是算法的实现，比如while(1) 死循环程序，因为不满足算法的有限性）。

总结：

算法具有4个性质：输入、输出、确定性、有限性

算法是方法，程序是方法的具体实现

当一个算法对每组输入数据，都能得到正确的输出数据，则称算法是正确的，否则称之为错误的。

2. 如何评价算法

为了实现同样一个需求，可以设计出各种不同的算法。

典型的，对一组数据排序，可以有直接插入法、冒泡排序法、堆排序等等；

简单的，实现从1累加到100，可以计算1+2+…+100，也可以计算50*(1+100)；

3. 如何评价一个算法的优劣？

对于程序设计而言，无非就是两个方面：

算法有多快？（时间效率）；

内存耗得多不多？（空间效率）

我们称之为算法的复杂度分析，包括上述两个方面，各自称为时间复杂度分析和空间复杂度分析。通常我们更关注的是算法的时间复杂度。

4. 时间复杂度分析

设问题规模为n，即输入数据的大小，时间复杂度记为T(n)

比如n个输入数据，需要做2n个基本运算，那么T(n) = 2n

下面的程序中，对一个n数据遍历了两次，其T(n) = 2*n

#include

#define n 5

int main()

{

int i;

int data[n] = ;

for(i=0;i

{

data[i] += 1;

}

for(i=0;i

{

printf("%d",data[i]);

}

return 0;

}

小编推荐一个学C语言/C++的学习裙【 二六三，六八八，二七六 】，无论你是大牛还是小白，是想转行还是想入行都可以来了解一起进步一起学习！裙内有开发工具，很多干货和技术资料分享！

再如嵌套两次循环，每次循环都是1至n，则其T(n) = n2

这里提的基本运算，可以是一条语句，也可以是一组语句，更具实际情况而定。

渐进时间复杂度

通常，我们分析算法的复杂度不需要考虑的这么具体，精确到2n，3n2+1等等，只需要考虑它的数量级就可以了，这就是渐进时间复杂度O(n)，也即是nà∞时，T(n) -> O(n)

备注：准确的说，O(n) 是渐进上界，相对的也就有渐进下界。但在实际分析时，通常直接说某某算法的时间复杂度为O(n)

O(n) 其实就是T(n)省略了低阶项和常数项

比如：

T(n) = 2*n 则O(n)=n， 实际中就称算法时间复杂度为n

T(n)= 3*n2 则O(n)=n2， 实际中就称算法时间复杂度为n2

T(n) =3* log(n)则O(n)=log(n)， 实际中就称算法时间复杂度为log(n)

空间复杂度分析

分析算法运行过程中所占用存储空间大小，其分析和时间复杂度类似。

如果使用1个基本空间单位，则空间复杂度为O(1)

如果使用n个基本空间单位，则空间复杂度为O(n)

这里说的空间复杂度实际中也是渐进空间复杂度。

以上就是结合实际使用，给出的算法的基本概念。一般来说，知道这些就够了。

如果有兴趣了解更多，可以自己查找更专业的资料来补充。

如果您觉得不错，请别忘了转发、分享、点赞让更多的人去学习， 您的举手之劳，就是对小乐最好的支持，非常感谢！