数据结构基础算法复杂度分析（一）概念篇

分类：数据结构与算法

为什么要进行算法分析？预测算法所需的资源预测算法的运行时间在给定输入规模时，所执行的基本操作数量，或者称为算法复杂度（Algorithm Complexity）如何衡量算法复杂度？磁盘访问数量网络包数量渐进复杂度（Asymptotic Complexity）算法的运行时间与什么相关？算法分析的种类

例

在一个长度为 n 的列表中顺序搜索指定的值，则

最坏情况：n 次比较；平均情况：n/2 次比较；最佳情况：1 次比较；而实际中，我们一般仅考量算法在最坏情况下的运行情况，也就是对于规模为 n 的任何输入，算法的最长运行时间。这样做的理由是：算法分析要保持大局观（Big Idea），其基本思路忽略掉那些依赖于机器的常量。关注运行时间的增长趋势。比如：T(n) = 73n3 + 29n3 + 8888 的趋势就相当于 T(n) = Θ(n3)。渐近记号（Asymptotic Notation）通常有 O、 Θ 和 Ω 记号法。Θ 记号渐进地给出了一个函数的上界和下界，，当只有渐近上界时使用 O 记号，当只有渐近下界时使用 Ω 记号。尽管技术上 Θ 记号较为准确，但通常仍然使用 O 记号表示。使用 O 记号法（Big O Notation）表示最坏运行情况的上界。例如，线性复杂度 O(n) 表示每个元素都要被处理一次；平方复杂度 O(n^2) 表示每个元素都要被处理 n 次。

例如：T(n) = O(n3) 等同于 T(n) ∈ O(n3)T(n) = Θ(n3) 等同于 T(n) ∈ Θ(n3).相当于：T(n) 的渐近增长不快于 n3。T(n) 的渐近增长与 n3 一样快。

注4：在算法导论中，采用记号 lg n = log2(n) ，也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍，所以当不在意这些常数因子时，我们将经常采用 "lg n"记号，就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然，因为很多算法和数据结构都涉及到对问题进行二分。

而通常时间复杂度与运行时间有一些常见的比例关系

计算代码块的渐进运行时间的方法有如下步骤

上一篇C++ 使用数组初始化 Vector下一篇数据结构基础算法复杂度分析（二）典例篇

顶0踩0

因为冲动会做下让自己无法挽回的事情。

相关文章：

你感兴趣的文章：

标签云：