算法与数据结构(算法简介及大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*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*1000*1000)+b$，若用$n$代表数据规模，则$T=k(n^3)+b$，若存在函数$g(n)$，使$T(n)=k*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*n*n*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)

本文地址：https://blog.csdn.net/m0_37422217/article/details/107072524