（2）Python代码耗时：0.7999107837677002

from time import *
k,n=0,10000000
start=time()
for i in range(n):k+=1
end=time()
print(end-start)

Python 的 for 循环很耗时，比 C++ 的 for 循环慢约 77 倍！

• 评测用的 OJ 服务器，性能可能比这个好一些，也可能差不多。
• 对于C++题目，如果题目要求“时间限制: 1s”，那么内部的循环次数 n 应该在 1 亿次以内；
• 对于同等规模的Python题目，时间限制一般是5 ~ 10s。

二、算法定义

算法(Algorithm) ：对特定问题求解步骤的一种描述，是指令的有限序列。有5个特征：

(1) 输入：一个算法有零个或多个输入。

(2) 输出：一个算法有一个或多个输出。

(3) 有穷性：一个算法必须在执行有穷步之后结束，且每一步都在有穷时间内完成。

(4) 确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。

(5) 可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。

1、计算复杂度

• 把 n 称为问题的数据规模，把程序的复杂度记为 O(n)。
• 复杂度只是一个估计，不需要精确计算。
• 例如在一个有 n 个数的无序数列中，查找某个数 a，可能第一个数就是 a，也可能最后一个数才是a。平均查找时间是 n/2 次，但是仍然把查找的时间复杂度记为 O(n)。
• 在算法分析中，规模 n 前面的系数被认为是不重要的。

2、有哪些复杂度

如下图所示：

三、算法评估 

• O(1) 计算时间是一个常数，和问题的规模 n 无关。
• 用公式计算时，一次计算的复杂度就是 O(1)，例如hash算法。
• 在矩阵 A|M|N| 中查找 i 行 j 列的元素，只需要一次访问 A[i][j]。
• O(logn) 计算时间是对数。
• 通常是以 2 为底的对数，每一步计算后，问题的规模减小一倍。例如在一个长度为 n 的有序数列中查找某个数，用折半查找的方法，只需要 logn 次就能找到。
• O(n) 计算时间随规模 n 线性增长。在很多情况下，这是算法能达到的最优复杂度，因为对输入的 n 个数，程序一般需要处理所有的数，即计算 n 次。例如查找一个无序数列中的某个数，可能需要检查所有的数。
• O(nlogn) 算法可能达到的最优复杂度。
• 快速排序算法是典型例子。
• O(n^2) 一个两重循环的算法，复杂度是O(n^2)。
• 例如冒泡排序，是典型的两重循环。
• O(n^3)、 O(n^4)等等。
• O(2n) 一般对应集合问题。
• 例如一个集合中有 n 个数，要求输出它的所有子集。
• O(n!) 在集合问题中，如果要求按顺序输出所有的子集，那么复杂度就是 O(n!)

1、分类

• 把上面的复杂度分成两类：
• 多项式复杂度，包括 O(1)、 O(n)、O(nlogn)、 O(nk)等，其中k是一个常数；
• O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3)
• 指数复杂度，包括O(2n)、O(n!)等。
• O(2n) < O(n!) < O(n^n)

2、易解问题——难解问题：用多项式时间来区分

• 一个算法是多项式复杂度：“高效”算法。
• 指数复杂度：“低效”算法。
• 多项式复杂度的算法，随着规模 n 的增加，可以通过堆叠硬件来实现，“砸钱”是行得通的；
• 指数复杂度的算法，增加硬件也无济于事，其增长的速度超出了想象力。

3、多项式函数与指数函数的增长对比

4、问题规模和可用算法（个人认为超级重要）

5、选择解题方法

• 竞赛所给的题目，一般都会有多种解法，它考核的是在限定时间和空间内解决问题。
• 如果条件很宽松，那么可以在多种解法中选一个容易编程的简单算法，以节约这一题的编码时间，有利于队员做更多的题。简单算法一般指暴力法，不用复杂算法和复杂数据结构，虽然代码的效率低下，但是思路和编码非常简单。
• 如果给定的时间和空间条件很苛刻，那么能选用的合适算法和数据结构就不多了。要得到100%的分数，需要用高效复杂的算法。如果不会复杂算法或时间来不及，可以用暴力法获得部分分数。

6、例题举例

求和  2022年第十三届蓝桥杯省赛，lanqiaoOJ 题号 2080

题目如下图：

（1）暴力法（可拿部分的分）

（2）前缀和 （AC）

以上， 算法复杂度分析

祝好！