2023CSP初赛备考复习 || 时间复杂度

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。

也就是说，为解决一个具体的问题，执行一系列程序指令，能够对一定规范的输入，在有限时间内获得所要求的输出。

例如如下问题：

题目描述

求前N项和

1+2+3+ …… +N 的值。

输入格式

输入

N

输出格式

输出

和

输入样例

输出样例

参考程序

需要如下程序指令完成

上述程序执行，涉及到输入，循环，输出等基本程序指令，主要时间耗费在for循环，且执行时间是随循环中N变化而变化的函数，分析算法执行时间通常使用算法的时间复杂度来衡量

算法的时间复杂度

算法的时间复杂度是一个函数，它定性描述该算法的运行时间，常用大O符号表述，它可以被认为是渐进，不考虑常数

对于足够大的输入规模，我们往往不需要花费很大力气计算太精确的结果，通常指关系增长级量，即算法的渐进效率

比如：

我们关心for循环的时间复杂度，而 int sum=0 忽略

因此时间复杂度为O(n),而不是O(n+1)

举例说明

1.O(1)

O(1)的时间复杂度可以这样理解：代码按顺序一行一行执行，没有任何的循环

比如：

无论有多少个这样的代码块，只要不出现循环，就可以被认为是O(1)，没有O(2)，O(3)

1个和几个都是O(1),不考虑常数

2.O(n)

O(n)的时间复杂度是与数据规模成线性的，比如：

循环体内循环了n次，这样的时间复杂度就是O(n)的，如果有多个这样的循环，只要不是循环嵌套，我们也认为是O(n)的，因为时间复杂的不考虑常数

3.O(n^2)

O(n^2)的时间复杂度很容易理解，就是循环里嵌套了一层循环，比如：

4.O(logn)

O(logn)的时间复杂度我们常常认为在数据规模为n下，代码执行的次数x满足c^x=n(c是一个较小的常数)，比如：

for循环中i每次*2，执行次数为logn次

常见的O(logn)的算法还有二分查找

5.O(nlogn)

O(nlogn)的时间复杂度就是在一个循环中嵌套了一个O(logn)的算法，比如：

6.O(2^n)

O(2^n)的时间复杂度常见于搜索，递归中，比如在用递归求斐波那契数的时候:

O(2^n)的时间复杂度是一个很不理想的时间复杂度，因此我们常常会使用一些技巧去尽可能地优化。

常用算法的时间复杂度

排序

1冒泡排序

正常冒泡排序需要一趟交换找到最大的,时间复杂度为O(n)，进行n-1躺排序,所以平均时间复杂度为O(N^2)

插入排序和选择排序的平均时间复杂度类似

最好: O(n)

如果其中一趟，没有任何交换，说明已经排好序了，可以提前推出

如果给出序列本身就是已经排好序的，一趟比较就排好序了，所以是 O(n)

平均: O(n^2)

最坏: O(N^2)

2插入排序

插入排序的思想为：从未排序的序列中取出一个，插入到前面已经排好序的合适位置

最好: O(n)

如果数列本身是排好序的，每次取出数据都是放到最后一个，进行取放各n次结束

所以最好时间复杂度为：O(n)

平均: O(n^2)

最坏: O(N^2)

3选择排序

每次从未排序的序列中，找一个最小的，放如已排序序列

每次找最小的时间复杂度为O(n),需要找n次，因此，平均时间复杂度为O(n^2)

序列中数据大小排序，对选择排序没有优化空间，因此最好时间复杂度也为O(n^2)

最好: O(n^2)

平均: O(n^2)

最坏: O(N^2)

4 快速排序

找到基准数，分成2各区间，再2个区间继续找基准数，二分下去

最好: O(nlogn)

平均: O(nlogn)

最坏: O(N^2)

5 归并排序

先中间分成2个区间，再子区间继续分，分到最底层逐渐合并回来

最好: O(nlogn)

平均: O(nlogn)

最坏: O(nlogn)

6 堆排序

使用完全二叉树的数据结构

最好: O(nlogn)

平均: O(nlogn)

最坏: O(nlogn)

7 基数排序

从低位到高位逐位排序

最好: O(d(n+rd))

平均: O(d(r+n))

最坏: O(d(r+n))

一般计算排序时间复杂度在 O(n)~O(nlogn)之间

8 希尔排序

最好: O(n)

平均: O(n^1.3)

最坏: O(n^2)

上述排序的稳定性：

冒泡排序，插入排序，归并排序，基数排序是稳定的，其余是不稳定的

分治时间复杂度-主定理

https://www.cnblogs.com/myeln/articles/16412060.html

复赛中评估时间复杂度

在一般在算法竞赛或者笔试题的时间限制是1秒，基本程序指令规模一般在10^8以内

对应相应时间复杂度可以接受的数据规模如下

O(n)算法能解决的数据范围在 n≤10^8

O(nlogn) 算法能解决的数据范围在 n≤10^6

O(n^2) 算法能解决的数据范围在 n≤5000

O(n^3) 算法能解决的数据范围在 n≤300

O(logn) 算法能解决的数据范围在 n

O(2^n) 算法能解决的数据范围在 n≤25