时间复杂度之大O表示法

时间复杂度之大O表示法

引用

CSDN

1.

https://m.blog.csdn.net/m0_63997099/article/details/136580416

大O表示法（Big O notation）是算法分析中用于描述算法复杂度的重要数学符号，它帮助我们理解算法执行时间与输入规模之间的关系。通过大O表示法，我们可以忽略常数因子和低阶项，专注于算法性能随输入规模增长的主要趋势。本文将从概念、常见时间复杂度、性质、结果等多个方面详细阐述大O表示法的含义和应用。

一、概念

O表示法：
设T(n)和g(n)是正整数集到正实数集上的函数。
称T(n) = O(g(n)) ，当且仅当存在一个正常数C和n0，使得对任意
的n≥n0，有T(n) ≤ C g(n)。
其中：n是算法输入的规模，如数组的长度，图的顶点数等；
一个算法时间复杂性是O(g(n))，称其时间复杂性的阶为g(n)；
大 O 符号定义了函数 T(n) 的一个上限，算法 的运行 时间（基本运算
次数）至多是g(n)的一个常数倍。
即：T(n)的增长速度至多与
g(n)的增长速度一样快。

二、常见时间复杂度

在每秒处理1亿次左右基本操作的计算机上，可以处理的1s对应的数据量量级：

• O(n)：10^7到10^8之间
• O(nlogn):10^5到10^6
• O(n^2)：10^3到10^4
• O(n^3)：10^2到10^3
• O(2^n)：20到30
• O(n!)：10到12

三、常用性质

（1）常系数，低次项以及低阶可忽略
（2）对数底可忽略
根据换底公式：
即时间复杂度的阶与对数底无关
以任何数为底的，都可以是O(logn)
（3）对数常数次幂可忽略

四、常用结果

（1）调和级数——O(logn)

（2）级数

五、大O表示法详解

大O表示法（Big O notation）是用来描述算法复杂度的数学符号，它表达了算法执行时间（或其他如空间占用）与输入规模之间的关系。大O表示法通过忽略常数因子和低阶项，提供了一种描述算法最坏情况运行时间增长趋势的方法。这种表示法帮助我们理解算法的效率和可扩展性，而不是给出精确的执行时间。

5.1 定义

5.2 常见的时间复杂度

• O(1)：常数时间复杂度。算法的执行时间不随输入规模的增长而增长，如访问数组中的某个元素。
• O(log n)：对数时间复杂度。算法的执行时间随输入规模的增长而以对数速度增长，典型的例子是二分查找。
• O(n)：线性时间复杂度。算法的执行时间随输入规模的增长而线性增长，如遍历数组。
• O(n log n)：线性对数时间复杂度。许多高效的排序算法（如快速排序、归并排序）都属于这一类。
• O(n^2)：平方时间复杂度。算法的执行时间随输入规模的增长而以平方速度增长，如简单的冒泡排序。
• O(2^n)：指数时间复杂度。算法的执行时间随输入规模的增长而以指数速度增长，典型的例子是求解斐波那契数列的递归算法。
• O(n!)：阶乘时间复杂度。算法的执行时间随输入规模的增长而以阶乘速度增长，如解决旅行商问题的暴力搜索算法。

5.3 为什么使用大O表示法

1. 简化分析：通过忽略常数因子和低阶项，大O表示法让我们能够集中关注算法性能随输入规模增长的主要趋势。
2. 易于比较：大O表示法提供了一种标准化的方法来比较不同算法的性能。
3. 独立于机器：由于它描述的是增长趋势而非具体执行时间，因此大O表示法的分析结果不依赖于特定的硬件或软件环境。

5.4 注意事项

• 大O表示法通常用于描述算法的最坏情况复杂度，但也可以用于平均情况或最佳情况复杂度的描述。
• 实际运行时间可能受到很多因素的影响（如CPU速度、内存大小等），大O表示法只是提供了一种理论上的性能度量。

理解和掌握大O表示法对于评估算法效率、进行算法设计和优化都非常重要。