本文首发公众号：架构精进，请移步，排版比较清晰。
经常有同学在 LeetCode 的题解中问解法的复杂度是多少。作为一个懒人，我一直在「逃避」这个问题，毕竟这东西听起来就这么「复杂」。
但本着对题解认真负责的态度（心虚），我想趁此机会做一个总结。下面我将通过一些较为经典的算法题聊一聊几种常见的时间复杂度。
什么是时间复杂度？算法的时间复杂度（Time complexity）是一个函数，用于定性描述算法的运行时间。
提出时间复杂度的目的是：分析与比较完成同一个任务而设计的不同算法。
大 O 符号时间复杂度通常用 大 O 符号（Big O notation）表示。大 O 符号 又被称为渐近符号，是用于描述函数 渐近行为。
举个例子，假设我们解决一个规模为 n 的问题要花费的时间为 T(n)T(n)：
T(n)=4n2−2n+2T(n)=4n2−2n+2
当 n 不断增大时，n2n2 开始占据主导地位，而其他各项可以被忽略，写作 T(n)=O(n2)T(n)=O(n2)。因此时间复杂度可被称为是 渐近 的。
常见复杂度比较但由于复杂度始终是 O(9×9)O(9×9)，加上使用哈希表来判断元素是否存在，所以算法的复杂度始为 O(1)O(1)。
对数时间若 T(n)=O(logn)T(n)=O(logn)，则称其具有对数时间。
常见例子：
二叉树相关操作二分查找为什么是 logn？什么是对数？首先，我们复习一下 对数。
对数 是幂运算的逆运算。假如 x=βyx=βy，那么就有 y=logβxy=logβx。其中：
ββ 是对数的底（基底）yy 就是 xx（对于底数 ββ）的对数那我们说一个算法的复杂度是 O(logn)O(logn)，那么 lognlogn 这个对数的底数去哪了？
换底公式二分查找如果一个算法的时间复杂度为 O(n)O(n)，则称这个算法具有线性时间。随着样本数量的增加，复杂度也随之线性增加。常表现为单层循环。
来看一到例题 求众数。这里我们用了摩尔投票法，时间复杂度为 O(n)O(n)。
若算法复杂度为 T(n)=O(nlogn)T(n)=O(nlogn)，则称这个算法具有线性对数时间。可以理解为执行了 n 次对数时间复杂度的操作。
有几种排序算法的平均时间复杂度都是线性对数时间，例如：
堆排序：前 K 个高频元素快速排序：颜色分类归并排序二次时间若算法复杂度为 T(n)=O(n2)T(n)=O(n2)，则称这个算法具有二次时间，即时间复杂度随着样本数量的增加呈平方数增长。常表现为双层循环。
常见的算法中有一写比较慢的排序算法，例如：
冒泡排序选择排序插入排序由于涉及的排序算法很多，若一一讲解的话就偏离这篇文章的侧重点了。如果大家对各类算法感兴趣可以参考：维基百科：排序算法。
算法是生活中的大智慧，而我们都是智慧的受益者。
1.《时间复杂度计算的例题 从经典算法题看时间复杂度》援引自互联网，旨在传递更多网络信息知识，仅代表作者本人观点，与本网站无关，侵删请联系页脚下方联系方式。
2.《时间复杂度计算的例题 从经典算法题看时间复杂度》仅供读者参考，本网站未对该内容进行证实，对其原创性、真实性、完整性、及时性不作任何保证。
3.文章转载时请保留本站内容来源地址，https://www.lu-xu.com/keji/347050.html