时间复杂度

名词

线性增长：O(N)

常数增长：O(1)

对数增长：O(logN)

N乘对数增长：O(NlogN)

对数

对数是数学中的一个概念，用来描述一个数与另一个数之间的关系。对数的定义是：如果a的x次方等于b，那么x就是以a为底b的对数，记作logₐb。其中，a被称为对数的底数，b被称为真数。对数可以帮助我们解决指数运算中的问题，例如求解指数方程、化简复杂的指数表达式等。对数有许多重要的性质和应用，在数学、科学和工程等领域中被广泛使用。

logN

logN是指以2为底的对数（即二进制对数），表示求解2的x次方等于N时的x值

当我们说一个问题或算法的时间复杂度是O(logN)时，意味着它的增长速度是以对数的方式进行的。这意味着随着输入规模N的增加，算法的运行时间或问题的规模增加得非常缓慢。可以将N视为真数，而对数部分则表示了增长的速度。因此，当N增加时，O(logN)的增长速度比线性增长（O(N)）要慢，但比常数增长（O(1)）要快。

举例

以log8为例，表示找到一个数x，使得2的x次方等于8。显然，2的3次方等于8，因此log2(8) = 3。

同理，log16 = 4，log32 = 5，依此类推。

NlogN

当我们说一个算法的时间复杂度是O(NlogN)时，表示该算法的运行时间随着输入规模N的增加而以N乘以对数的速度增长。

举例

归并排序是一个具有O(NlogN)时间复杂度的排序算法。它的工作原理是将数组不断划分为更小的子数组，然后按顺序合并这些子数组，直到得到一个完全排序的数组。

假设我们有一个长度为N的无序数组，数组元素为随机排列的整数。我们使用归并排序对数组进行排序。在归并排序的过程中，我们将数组划分为更小的子数组，然后按顺序合并这些子数组。每一次合并都需要比较和移动数组元素。在每个合并步骤，需要进行的比较和移动操作的总次数为N。总的合并步骤数为logN。

因此，在归并排序中，总的比较和移动操作次数为N * logN，所以归并排序的时间复杂度是O(NlogN)。