当前位置：首页 > article >正文

算法复习，数据结构，算法特性，冒泡法动态演示，复杂度，辗转相除法*，寻找最大公因数

article 2024/9/24 7:18:24

算法复习

知识点

1. 程序 = 数据结构 + 算法

2. 算法：

求解问题的策略
数据结构：问题的数学模型
程序：微计算机处理问题编制的一组指令

3. 特性

有穷性：算法在执行有穷步后能结束
确定性：每一指令有确切的含义，无二义
可行性：每一操作都可以通过已经实现的基本运算执行有限次来实现
输入：零个或多个输入
输出：一个或多个输出

4. 算法的时间复杂度

针对问题指定基本运算，计数算法所做的基本运算次数最好、最坏、平均情况下的时间复杂度
**最坏情况下的时间复杂度 **：算法求解输入规模为n的实例所需要的最长时间W(n).
最好情况下的时间复杂：算法求解输入规模为n的实例所需要的最短时间B(n).
平均情况下的时间复杂度：在指定输入的概率分布下，算法求解输入规模为n的实例所需要的平均时间 A(n).

5. 常见算法

冒泡法

一次排序就可以把最大或最小的排序出来

##the most import exchange 核心代码  

for i in range(len(a)):
    if a[i]>a[i+1]:
        a[i],a[i+1] = a[i+1],a[i]
        ##swap(a[i],a[i+1])
       
## 可运行代码
for j in range(0,len(a)-1):
    for i in range(0,len(a)-1-j):
        if a[i]>a[i+1]:
            a[i], a[i + 1] = a[i + 1], a[i]

复杂度
- 最优O（n）
- 最差O（n*（n-1））
- 平均O（n“2）

1. 顺序查找
  - ```
  ###核心代码
  for i in range(len(a)):
  	if des == a[i]:
  		return i
  	
```
- 时间复杂度:
  - 最优O(1) 一次找到
  - 最差O(n)最后找到
  - 平均: O(n+1/2)
3. 1.1 Euclid(m, n)，也叫辗转相除法 寻找最大公因数
  - 输入：非负整数 m, n，其中m与n不全为0
  - 输出：m 与 n 的最大公约
  - 相关链接:(12 封私信 / 18 条消息) GCD算法描述 - 知乎 (zhihu.com)
  - ```
  ### 理解 首先假设最大公因数为 t,M>N   那么 m = bt   n = at  b>a  
  ### 核心代码
  while n>0
  	m,n = n,m%n
      return m
      ###n最终n会被m整除 这个时候m就是t
```
- 学习链接:辗转相除法介绍 - 知乎 (zhihu.com)