算法复杂度分析-蓝桥杯

忘是亡心i 2023-09-24 17:38 30阅读 0赞

# **一、计算资源** #

## **1.程序运行需要的资源有两种** ##

*  时间：程序运行需要的时间

*  空间：程序运行需要的存储空间

\------>资源是有限的

![56d7cfadd5184cd3aaddef608c422993.png][]

## **2.不同编程语言，时间限制不一样，空间限制也不一样。** ##

![4cbe87511e014ee7bda0c20841f5cb1f.png][]

![3c61b74fc1c14eab8889a3fbf39d9f9d.png][]

## **3.时间和空间限制** ##

*  程序必须在限定的时间和空间内运行结束。

*  问题的“有效”解决，不仅在于能否得到正确答案，更重要的是能在合理的时间和空间内给出答案。

*  “好”算法:效率高; 思路复杂，编码长。

*  “坏”算法:慢;思路简单，编码短。

## **4.实例比较不同代码的运行时间** ##

![e70a1b122bba44b5bda15c177f55d641.png][]

## **5.运行时间** ##

*  评测用的OJ服务器，性能可能比这个好一些也可能差不多。

*  对于C++题目，如果题目要求“时间限制1s”那么内部的循环次数n在1千万次;

*  对于同等规模的Python题目，时间限制一般是5~10s。

# **二、算法的定义** #

## **1.定义** ##

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

## **2.特征** ##

*  输入:一个算法有零个或多个输入。

*  输出:一个算法有一个或多个输出。

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

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

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

## **3.计算复杂度** ##

*  把n称为问题的数据规模，把程序的复杂度用O()表示。

*  复杂度只是一个估计，不需要精确计算。

*  例如在一个有n个数的无序数列中，查找某个数a，可能第一个数就是a，也可能最后一个数才是a。平均查找时间是n/2次，把查找的时间复杂度记为O(n)。

*  在算法分析中，规模n前面的系数被认为不重要

![0f1cb1871a88485798fe6b7daf2a86d9.png][]

## **4.算法的评估** ##

*  O(1) 计算时间是一个常数，和问题的规模n无关。用公式计算时，一次计算的复杂度就是0(1)，例如hash算法。在矩阵A\[M\]\[N\]中查找i行i列的元素，只需要一次访问A\[i\]\[i\]。

*  O(logn) 计算时间是对数。通常是以2为底的对数，每一步计算后，问题的规模减小一倍例如在一个长度为n的有序数列中查找某个数，用折半查找的方法，只需要logn次就能找到。

*  O(n) 计算时间随规模n线性增长。在很多情况下，这是算法能达到的最优复杂度，因为对输入的n个数，程序一般需要处理所有的数，即计算n次。例如查找一个无序数列中的某个数，可能需要检查所有的数。

*  O(nlogn)算法可能达到的最优复杂度。快速排序算法是典型例子

*  O(n2) 一个两重循环的算法，复杂度是O(n2)。例如冒泡排序，是典型的两重循环。

*  O(n3)、O(n4)等等。

*  (O2n)一般对应集合问题。例如一个集合中有n个数，要求输出它的所有子集。

*  O(n!) 排列问题，复杂度是O(n!)。

## **5.算法的评估** ##

把上面的复杂度分成两类:

*  多项式复杂度，包括O(1)、O(n)、O(nlogn)、O(nk)等，其中k是一个常数;O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)。

*  指数复杂度，包括O(2n)、O(n!)等。O(2n)<O(n!)<O(nn)。

## **6.多项式函数与指数函数的增长对比** ##

![04a519c2c4e4438e81dd30693b1a81b9.png][]

## **7.问题规模和可用算法** ##

![4190ae6f354349ccaef210b7ff468acf.png][]

## **8.选择解题方法** ##

*  竞赛所给的题目，一般都会有多种解法，它考核在限定时间和空间内解决问题。

*  如果条件很宽松，那么可以在多种解法中选一个容易编程的简单算法，以节约这一题的编码时间。简单算法一般指暴力法，不用复杂算法和复杂数据结构，虽然代码的效率低下，但是思路和编码非常简单。

*  如果给定的时间和空间条件很苛刻，那么能选用的算法和数据结构就难了。

*  要得到I00%的分数，需要用高效复杂的算法。

*  如果不会复杂算法或时间来不及，可以用暴力法获得部分分数。

# **三、例题** #

![7a7b057b2d36452ea6945b3eaa43c15a.png][]

## **1.暴力法** ##

![6da88642e08242d3b601e75053d5761d.png][]

![7d4577804c574bfc934eec4fa7cc6bab.png][]

![5e37bce12b62451c8f3688d7b15ad6c9.png][]

## **2.前缀和** ##

![fc019f5e8c2a414283465924968ab406.png][]

![e3e2fcc1e1c54645abbac72166a8cd87.png][]

[56d7cfadd5184cd3aaddef608c422993.png]: https://img-blog.csdnimg.cn/img_convert/56d7cfadd5184cd3aaddef608c422993.png
[4cbe87511e014ee7bda0c20841f5cb1f.png]: https://img-blog.csdnimg.cn/img_convert/4cbe87511e014ee7bda0c20841f5cb1f.png
[3c61b74fc1c14eab8889a3fbf39d9f9d.png]: https://img-blog.csdnimg.cn/img_convert/3c61b74fc1c14eab8889a3fbf39d9f9d.png
[e70a1b122bba44b5bda15c177f55d641.png]: https://img-blog.csdnimg.cn/img_convert/e70a1b122bba44b5bda15c177f55d641.png
[0f1cb1871a88485798fe6b7daf2a86d9.png]: https://img-blog.csdnimg.cn/img_convert/0f1cb1871a88485798fe6b7daf2a86d9.png
[04a519c2c4e4438e81dd30693b1a81b9.png]: https://img-blog.csdnimg.cn/img_convert/04a519c2c4e4438e81dd30693b1a81b9.png
[4190ae6f354349ccaef210b7ff468acf.png]: https://img-blog.csdnimg.cn/img_convert/4190ae6f354349ccaef210b7ff468acf.png
[7a7b057b2d36452ea6945b3eaa43c15a.png]: https://img-blog.csdnimg.cn/img_convert/7a7b057b2d36452ea6945b3eaa43c15a.png
[6da88642e08242d3b601e75053d5761d.png]: https://img-blog.csdnimg.cn/img_convert/6da88642e08242d3b601e75053d5761d.png
[7d4577804c574bfc934eec4fa7cc6bab.png]: https://img-blog.csdnimg.cn/img_convert/7d4577804c574bfc934eec4fa7cc6bab.png
[5e37bce12b62451c8f3688d7b15ad6c9.png]: https://img-blog.csdnimg.cn/img_convert/5e37bce12b62451c8f3688d7b15ad6c9.png
[fc019f5e8c2a414283465924968ab406.png]: https://img-blog.csdnimg.cn/img_convert/fc019f5e8c2a414283465924968ab406.png
[e3e2fcc1e1c54645abbac72166a8cd87.png]: https://img-blog.csdnimg.cn/img_convert/e3e2fcc1e1c54645abbac72166a8cd87.png