正文第一个公众号：结构精进。 请移动。 排版清晰。

有同学经常问LeetCode的问题解决方法的复杂性是多少。 作为懒人，我一直在“逃避”这个问题，但最终这听起来这么“复杂”。

但是，我想以对解决问题认真负责的态度，借此机会总结一下。 在这里，我们用更典型的算法问题来谈谈一些常见的时间复杂性。

什么是时间复杂度？

算法的时间复杂度是用于定性描述算法执行时间的函数。

提出时间复杂度的目的是分析和比较为完成相同任务而设计的不同算法

分析算法的结果意味着算法所需的资源。 虽然有时会对内存、通信带宽、计算机硬件等资源感兴趣，但通常希望测量计算时间。 一般来说，通过分析求解某一问题的几个候选算法，可以选择最有效的算法。 这个分析可能表明有多种可行的候选算法，但是在这个过程中，我们往往可以放弃一些不好的算法。 —— 《算法导论》

大 O 符号

小时的复杂度通常用较大的o符号(Big O notation )表示。 大o符号也称为渐近符号，用于描述函数的渐近行为。

例如，假设解决规模为n的问题所需的时间为t(n ) t ) n )。

t(n )=4n 22 n2) ) n )=4n 22 n 2

当n变大时，n2n2开始占据主导地位，其他项目可以忽略，写成t(n )=o ) n2 ) t ) (n )=o ) n2 )。 因此，时间的复杂性可以称为渐近。

常见复杂度比较

一般时间复杂度的比较

常数时间

如果算法t(n ) t ) n )的上限与输入的大小无关，则其具有常数时间，表示为t ) n )=o )1) t ) n )=o )1)。

常见的例子如下

要访问数组中的各个元素哈希表

别被循环所迷惑

，例如这个问题的有效数独，需要判断9x9的网格中数独是否有效。

思路：用哈希表记录行、列和小正方形区域出现的数字，判断遍历中数字是否出现在这三个范围内即可，出现时返回False。

问题如下。

问题的解决循环如下：

但是，复杂度总是o(9)9) o )9)，因为使用散列表判断有无要素，所以算法的复杂度从o )1) o )1)开始。

对数时间

t(n )=o ) logn )的情况下，据说具有对数时间。

常见例子：

用二叉树相关的操作两分钟查找

为什么是 logn？

什么是对数？

。 首先复习对数。

对数是幂运算的逆运算。 如果设x=yx=y，则有y=logxy=logx的情况。 其中：

是对数的底(基) yy是xx )的对数。 对于基数)算法的复杂度为o ) Logn ) o ) Logn )，那么lognlogn这个对数的底数去了哪里？

换底公式

二分查找

。

如果

线性时间

算法的时间复杂度为o(n ) o ) n )，则该算法称为具有线性时间。 随着样本数量的增加，复杂性也呈线性增加。 多表现为单层循环。

一到例题就来求群众的数量。 这里使用的是cjdqd投票法，时间复杂度为o(n ) o ) n )。

线性对数（准线性）时间

算法的复杂度为t(n )=o ) nlogn ) t ) n )=o ) nlogn )时，该算法被称为具有线性对数时间。 可以理解为对数小时复杂度的操作执行了n次。

一些排序算法的平均时间复杂度是线性对数时间。 例如，如下所示。

排序：前k个高频元素的快速排序：颜色聚类排序

二次时间

算法的复杂度为t(n )=o ) n2 ) t ) n )=o ) n2时，该算法具有二次时间，即样本数为经常表现为双重循环。

在常见的算法中，有写得慢的排序算法。 例如：

气泡排序选择排序插入排序由于相关的排序算法很多，逐一说明就会偏离本文的重点。 如果大家对各种算法感兴趣，请参阅维基百科：排序算法。

算法是生活中的一大智慧，我们都是智慧的受益者。