时间复杂度分为几种

按照快到慢排序

  1. O(1)
  2. O(logN)
  3. O(N)
  4. O(NlogN)
  5. O(N^2)

例子

O(1)

  1. hashset
  2. hashmap
  3. 数组下标

O(logN)

  1. 折半查找
  2. 树形遍历

O(N)

  1. list 查询值
  2. 数组查询值

O(NlogN)

进阶排序
  1. 快排
  2. 堆排
  3. 归并

O(N^2)

简单排序
  1. 冒泡
  2. 插入
  3. 选择

ChatGPT

时间复杂度是衡量算法执行时间随输入规模增长而变化的度量。它用大O符号表示，表示算法执行时间的增长率。

在算法分析中，常见的时间复杂度有以下几种：

  1. 常数时间复杂度（O(1)）：算法的执行时间不随输入规模的增长而变化。无论输入数据量多少，算法都需要固定的时间完成。

  2. 对数时间复杂度（O(logN)）：算法的执行时间随着输入规模的增长而增加，但是增长速率较慢。典型的例子是二分查找算法。

  3. 线性时间复杂度（O(N)）：算法的执行时间与输入规模呈线性关系。如果输入规模增加一倍，算法的执行时间也会增加一倍。

  4. 线性对数时间复杂度（O(NlogN)）：算法的执行时间介于线性时间复杂度和平方时间复杂度之间。常见的例子是快速排序和归并排序等排序算法。

  5. 平方时间复杂度（O(N^2)）：算法的执行时间随输入规模的增长而呈二次方增长。例如，嵌套循环的算法通常具有平方时间复杂度。

  6. 指数时间复杂度（O(2^N)）：算法的执行时间随输入规模的增长而呈指数级增长。通常与暴力解法或穷举法相关。

除了以上常见的时间复杂度，还有更高阶的复杂度，如多项式时间复杂度（O(Nk)）、指数多项式时间复杂度（O(kN)）等。这些复杂度通常表示算法的效率较低，应尽量避免使用。

需要注意的是，时间复杂度只考虑算法执行时间与输入规模的关系，并不考虑具体的执行时间。因此，两个具有相同时间复杂度的算法，在实际执行中可能有较大的性能差异。时间复杂度仅提供了一种用于比较算法执行效率的指标。