博客

按照快到慢排序

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(N

^{k)）、指数多项式时间复杂度（O(k}

N)）等。这些复杂度通常表示算法的效率较低，应尽量避免使用。

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