算法研究内容&算法有关概念

1.1调度问题与投资问题
1. 调度问题
问题&建模

2. 贪心算法: 加工时间短的先做,加工时间从小到大排序(有反例 根据实际问题使用)
3. 算法设计:
1.问题建模
2.选择什么算法?如何描述这个算法?
3.这个算法是否对所有实例都得到最优解?如何证明?
4.如果不是,能否找到反例?
4. 投资问题
问题&建模

建模:

5. 蛮力算法:
算法&效率

效率:

6.小结: 问题求解的关键

• 建模: 对输入参数和解给出形式化或半形式化的描述
  
• 设计算法: 采用什么算法设计技术,正确性--是否对所有的实例都得到正确的解
  
• 分析算法--效率
  

1.2问题的计算复杂度: 排序问题
1.排序算法的效率: 以元素比较作基本运算
各算法比较

1.1插入排序

运行实例

1.2冒泡排序

运行实例每一次巡回,最大数放在最后,下一次巡回停止在上次最后一次交换处

1.3快速排序

运行实例把首元素当作划分标准,从最后一个数从前开始找第一个比首元素小的数,从前面向后面找第一个比首元素大的数,两者交换.

1.4二分归并排序

运行实例中间分开两组,先递归排序,再挨个取第一个数比较,小的取出来

2.问题的计算复杂度分析

3.小结:

• 几种排序算法简介:插入排序、冒泡排序、快速排序、归并排序
  
• 排序问题的难度估计--界定什么是最好的排序算法
  

1.3NP-hard问题与计算复杂性
1.NP-hard问题

典型问题1.1 货郎问题详情问题:

建模与算法:输入

1.2 0-1背包问题详情问题:

建模与算法:

1.3 双机调度问题详情问题:

建模与算法:

• NP-hard问题小结:
  
  
  
  • 这样的问题有数千个,大量存在于各个应用领域
    
  • 至今没找到有效算法: 现有的算法的运行时间是输入规模的指数或更高阶函数
    
  • 至今没有人能够证明对于这类问题不存在多项式时间的算法
    
  • 从是否存在多项式时间算法的角度看,这些问题彼此是等价的,这些问题的难度处于可有效计算的边界
    
  
  

Algorithm + Data Structure = Programming

好的算法: 提高求解问题的效率&节省存储空间
算法的研究目标:

• 问题 -> 建模并寻找算法
  
• 算法 -> 算法的评价
  
• 算法类 -> 问题复杂度估计
  
• 问题类 -> 能够求解的边界
  

计算复杂性理论的核心--NP完全理论

1.4算法及其时间复杂度
1.问题及实例

详情

• 问题: 需要回答的一般性提问,通常含若干参数
  
• 问题描述:
  定义问题参数(集合,变量,函数,序列等)
  说明每个参数的取值范围及参数间的关系
  定义问题的解
  说明解满足的条件(优化目标或约束条件)
  
• 问题实例: 参数的一组赋值可得到问题的一个实例
  

2.算法

详情

• 算法:
  有限条指令的序列
  这个指令序列确定了解决某个问题的一系列运算或操作
  
• 算法A解决问题P:
  把问题P的任何实例作为算法A的输入,每步计算是确定性的,A能够在有限步停机,输出该实例的正确的解
  

3.基本运算与输入规模

详情

算法基本运算次数可表为输入规模的函数

给定问题和基本运算就决定了一个算法类

• 3.1 输入规模
  
  
  
  • 排序: 数组中元素个数n
    
  • 检索: 被检索数组的元素个数n
    
  • 整数乘法: 两个整数的位数m,n
    
  • 矩阵相乘: 矩阵的行列数i,j,k
    
  • 图的遍历: 图的顶点数n,边数m
    ...
    
  
  
• 3.2基本运算
  
  
  
  • 排序: 元素之间的比较
    
  • 检索: 被检索元素x与数组元素的比较
    
  • 整数乘法: 每位数字相乘(位乘)1次m位和n位整数相乘要做mn次位乘
    
  • 矩阵相乘: 每对元素乘1次 ij矩阵与jk矩阵相乘要做ijk次乘法
    
  • 图的遍历: 置指针
    ...
    
  
  

4.时间复杂度

概念

• 4.1最坏时间复杂度W(n)
  算法求解输入规模为n的实例所需要的最长时间
  
• 4.2平均时间复杂度A(n)
  在给定同样规模为n的输入实例的概率分布下,算法求解这些实例所需要的平均时间
  计算公式
  
  
  
  

顺序检索算法问题  实例

最坏情况的时间估计:

平均情况的时间估计:

改进

最坏时间复杂度: W(n) = n
平均时间复杂度: A(n) = n/2

1.5算法的伪码表示
1.关键字

• 赋值语句: ←
  
• 分支语句: if ... then ... [else...]
  
• 循环语句: while, for, repeat until
  
• 转向语句: goto
  
• 输出语句: return
  
• 调用: 直接写过程的名字
  
• 注释: //...
  

2.例子

求最大公约数输入: 非负整数m,n,其中m与n不全为0 输出: m与n的最大公约数
伪码表示:

• while m > 0 do
  
• r ← n mod m
  
• n ← m
  
• m ← r
  
• return n
  

运行实例:

改进的顺序检索输入: 数组 L[1...n], 元素从小到大排列,数x.输出: 若x在L中,输出x的位置下标j;否则输出0
伪码表示:

• j ← 1
  
• while j  0 and x < A do
  
• A[i+1] ← A
  
• i ← i-1
  
• A[i+] ← x
  

运行实例:

二分归并排序MergeSort(A,p,r)输入: 数组A[p...r]
输出: 按递增顺序排序的数组A
伪码表示:

• if p < r
  
• then q ← [(p+r)/2]
  
• MergeSort(A,p,q)
  
• MergeSort(A,q+1,r)
  
• Merge(A,p,q,r)
  

MergeSort 有递归调用,也调用Merge过程
3.小结:

• 伪码不是程序代码,只是给出算法的主要步骤
  
• 伪码中允许过程调用
  

1.6函数的渐进的界--阶
1.五种表示函数的阶的符号
111
大O符号

例子:

大Ω符号

例子:

小o符号

小ω符号

例子:

大Θ符号

2.小结:

1.7有关函数渐进的界的定理
1.设函数f、g、h的定义域为自然数集合

定理

• 定理一
  
  
  
  估计函数的阶:
  
  
  
  
• 定理二: 函数的阶之间的关系具有传递性
  
  
  
  阶排序:
  
  
  
  
• 定理三
  
  
  
  

2.小结:

• 估计函数的阶的方法: 计算极限
  
• 阶具有传递性
  
• 对数函数的阶低于幂函数的阶,多项式函数的阶低于指数函数的阶
  
• 算法的时间复杂度是各步操作时间之和,在常数步的情况下取最高阶的函数即可
  

1.8几类重要的函数及性质
基本函数类: 阶的高低

函数对数函数简化符号:

性质:

指数函数与阶乘

取整函数定义:

实例:

应用: 二分检索

性质:

证明性质(1):

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！