首页 > 代码库 > 【数据结构学习笔记（C#描述）】（二）算法分析

【数据结构学习笔记（C#描述）】（二）算法分析

2024-07-04 05:28:14   224人阅读

由上一章的内容可知软件质量的重要特征之一就是能够高效的利用资源（运行效率），因此我们就要考虑如何创建出能够高效利用CPU及内存的数据结构与算法。而算法分析的目的就是为了让我们能够认识到算法对于资源的利用效率。
 
我们要想分析算法的效率，就需要找到一个评价算法效率的标准及方法。
一般我们如果能快速的利用CPU就会更好的节省时间，因此在时间层面上我们的评价标准就是时间复杂度，而如果我们能够较好的利用内存的话我们将会节省更多的内存空间，因此在空间层面上我们的评价标准就是空间复杂度。
所谓时间复杂度和空间复杂度就是 待解问题的大小对应的时间和空间的使用，即增长函数：f（n），n代表问题的大小。
 
然而，我们在分析算法的时候并不总是需要知道算法的确切复杂度。而更关心的是算法的渐进复杂度也就是当n增加的时候，函数的一般特性。
例如 增长函数：f（n）=15n^2+45n
随着n的增长，n^2项的增长将元快于n项的增长。
 
也就是说我们更关心代码的阶次：忽略算法的增长函数中常量与其他次要项，只保留主项而得出的。算法的阶次为增长函数提供了一个上界。
阶次为n^2的时间复杂度我们记做O（n^2） 阶次为n的时间复杂度我们记做O(n) ，我们称这话总记录方法为大O记法
 
增长函数 阶次 标记
f(n)=17 O(1) 常量型
f(n)=3log n
O(log n)
 对数型
f(n)=30n-4
O(n)
 线性
f(n)=12nlog n +100n
O(nlog n)
 nlogn
f(n)=3n^2+5n-2
O(n^2)
 平方型
f(n)=8n^3+3n^2
O(n^3)
 立方型
f(n)=2^n+18n^2+12
O(2^n)
 指数型


联系
我们