时间复杂度之大O表示法

时间复杂度之大O表示法

引用

CSDN

1.

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

一、概念

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表示法对于评估算法效率、进行算法设计和优化都非常重要。