算法与数据结构(part1)--算法简介及大O表示法

学习笔记，仅供参考

---

文章目录

算法与数据结构--基于python数据结构和算法简介算法引入例题A算法的概念例题A的优化 算法效率的衡量时间复杂度与大O记法例题A的时间复杂度如何理解大O记法最坏时间复杂度时间复杂度的几条基本计算规则常见的时间复杂度

---

算法与数据结构–基于python

数据结构和算法简介

什么是数据结构

数据结构就是一些有关系的数据的集合，有顺序表，链表，栈，队列，树，图等结构，

我们的程序就等于数据结构+算法。

什么是算法

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制；不同的算法可能用不同的时间、空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量；算法就是一种思路.

数据结构和算法的用处

写出的程序可以更高效；

面对一些复杂问题可能无从下手，数据结构和算法可以锻炼逻辑思维。

算法引入

例题A

如果 a+b+c=1000，且 a²+b²=c²（a,b,c为自然数），如何求出所有a、b、c可能的组合？（不使用数学公式）

枚举法：

import time start = time.time() for a in range(1001): # a取完让b去取 for b in range(1001): for c in range(1001): if a + b + c == 1000 and a**2 + b**2 == c**2: print(a,b,c) end = time.time() print('finish') print('程序用时：',(end-start))

运行结果：

0 500 500 200 375 425 375 200 425 500 0 500 finish 程序用时： 829.0995240211487

算法的概念

算法是计算机处理信息的本质，因为计算机程序本质上是用一个算法来告诉计算机确切的步骤，进而执行一个指定的任务。当算法在处理信息时，会从输入设备或数据的存储地址读取数据，把结果写入输出设备或某个存储地址供以后再调用。

算法是独立存在的一种解决问题的方法和思想，对于算法而言，实现的语言并不重要，重要的是思想，算法有不同的语言实现版本（如C、Java、Python等）

算法的五大特性

输入: 算法具有0个或多个输入;

输出: 算法至少有1个或多个输出;

有穷性: 算法在有限的步骤之后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完成;

确定性：算法中的每一步都有确定的含义;

可行性：算法的每一步都是可行的.

例题A的优化

import time start = time.time() for a in range(1001): # a取完让b去取 for b in range(1001 - a): # a,b已经确定了 c = 1000 - a - b if a**2 + b**2 == c**2: print(a,b,c) end = time.time() print('finish') print('程序用时：',(end-start))

运行结果：

0 500 500 200 375 425 375 200 425 500 0 500 finish 程序用时： 2.3102197647094727

最直观的评判算法优劣的标准，就是运行时间，可以看到改进的算法运行时长明显小于枚举法，所以改进的算法一定程度上优于枚举法。

算法效率的衡量

执行时间反应算法效率

实现算法程序的执行时间可以反应出算法的效率，即算法的优劣

单纯依据时间衡量可信么？

单纯依靠运行的时间来比较算法的优劣并不一定是客观准确的；

程序的运行离不开计算机环境（包括硬件和操作系统），这些客观原因会影响程序运行的速度并反应在程序的执行时间上。

时间复杂度与大O记法

假定计算机执行算法每一个基本操作的时间是固定的一个时间单位，那么有多少个基本操作就代表会花费多少时间单位。

虽然对于不同的机器环境而言，确切的单位时间是不同的，但是对于算法进行多少个基本操作（即花费多少时间单位）在规模数量级上却是相同的，由此可以忽略机器环境的影响，而客观的反应算法的时间效率。

对于算法的时间效率，我们可以用大O记法来表示。

大O记法：对于单调的整数函数$f$，如果存在一个整数函数$g$和实常数$c>0$，使得对于充分大的n总有$f(n)<=c\ast g(n)$，就说函数$g$是$f$的一个渐近函数（忽略常数），记为$f(n)=O(g(n))$。也就是说，在趋向无穷的极限意义下，函数$f$的增长速度受到函数$g$的约束，亦即函数$f$与函数$g$的特征相似。

时间复杂度：假设存在函数$g$，使得算法A处理规模为n的问题示例所用时间为$T(n)=O(g(n))$，则称$O(g(n))$为算法A的渐近时间复杂度，简称时间复杂度，记为$T(n)$

例题A的时间复杂度

我们用$T$表示时间复杂度，则对于枚举法来说，其时间复杂度为$T=k(1000\ast 1000\ast 1000)+b$，若用$n$代表数据规模，则$T=k(n^3)+b$，若存在函数$g(n)$，使$T(n)=k\ast g(n)+b$，因为$k$和$b$不影响大局，即相比于$g(n)$的形式来说，对时间的影响微不足道，所以我们抛弃$k$和$b$，则算法的趋势为$T(n)=O(g(n))$

如何理解大O记法

对于算法进行特别具体的细致分析虽然很好，但在实践中的实际价值有限。对于算法的时间性质和空间性质，最重要的是其数量级和趋势，这些是分析算法效率的主要部分.

而计量算法基本操作数量的规模函数中那些常量因子可以忽略不计。例如，可以认为$3n^2$和$100n^2$属于同一个量级，如果两个算法处理同样规模实例的代价分别为这两个函数，就认为它们的效率差不多，都为$n^2$级.

最坏时间复杂度

分析算法时，存在几种需要考虑的情况：

算法完成工作最少需要多少基本操作，即最优时间复杂度。

算法完成工作最多需要多少基本操作，即最坏时间复杂度。

算法完成工作平均需要多少基本操作，即平均时间复杂度。

我们主要关注算法的最坏情况，亦即最坏时间复杂度。

时间复杂度的几条基本计算规则

基本操作，即只有常数项，认为就是$O(1)$顺序结构，时间复杂度按加法进行计算循环结构(for)，时间复杂度按乘法进行计算分支结构(if)，时间复杂度为分支中的时间复杂度的最大值

刚才的例题A中就存在分支结构(if)和循环结构(for)：

for a in range(1001): # a取完让b去取 for b in range(1001): for c in range(1001): if a + b + c == 1000 and a**2 + b**2 == c**2: print(a,b,c)

时间复杂度：$T(n)=n\ast n\ast n\ast max(1,0)=n^3$

当我们的程序遇到if时，可能会执行if语句体里的内容，也可能不执行，所以分支结构if中最多有1次操作，最少为0次，而我们计算时间复杂度时，则用最大操作次数1来计算。

常见的时间复杂度

执行次数函数举例阶非正式术语12$O(1)$常数阶2n+3$O(n)$线性阶3n²+2n+1$O(n^2)$平方阶5log2n+20$O(logn)$对数阶2n+3nlog2n+19$O(nlogn)$$nlogn$阶6n³+2n²+3n+4$O(n^3)$立方阶2^n$O(2^n)$指数阶 常见时间复杂度之间的关系

所消耗的时间从小到大：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2^n) < O(n!) < O(n^n)