算法研究内容&算法有关概念
1.1调度问题与投资问题1. 调度问题
问题&建模
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029230606723-586212831.png
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029231707425-17784917.png
2. 贪心算法: 加工时间短的先做,加工时间从小到大排序(有反例 根据实际问题使用)
3. 算法设计:
1.问题建模
2.选择什么算法?如何描述这个算法?
3.这个算法是否对所有实例都得到最优解?如何证明?
4.如果不是,能否找到反例?
4. 投资问题
问题&建模
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029232151370-1438224482.png
建模:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029232250618-525030004.png
5. 蛮力算法:
算法&效率
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029232405057-713353388.png
效率:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029232450900-1886612979.png
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251029232507472-871955799.png
6.小结: 问题求解的关键
[*]建模: 对输入参数和解给出形式化或半形式化的描述
[*]设计算法: 采用什么算法设计技术,正确性--是否对所有的实例都得到正确的解
[*]分析算法--效率
1.2问题的计算复杂度: 排序问题
1.排序算法的效率: 以元素比较作基本运算
各算法比较
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251030205557787-388119864.png
1.1插入排序
运行实例https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251030210008381-44855325.png
1.2冒泡排序
运行实例每一次巡回,最大数放在最后,下一次巡回停止在上次最后一次交换处https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251030210710281-644827080.png
1.3快速排序
运行实例把首元素当作划分标准,从最后一个数从前开始找第一个比首元素小的数,从前面向后面找第一个比首元素大的数,两者交换.https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031131515909-1799030353.png
1.4二分归并排序
运行实例中间分开两组,先递归排序,再挨个取第一个数比较,小的取出来https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031131727213-788402900.png
2.问题的计算复杂度分析
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031132017162-408848297.png
3.小结:
[*]几种排序算法简介:插入排序、冒泡排序、快速排序、归并排序
[*]排序问题的难度估计--界定什么是最好的排序算法
1.3NP-hard问题与计算复杂性
1.NP-hard问题
典型问题1.1 货郎问题详情问题:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031223039154-374476714.png
建模与算法:输入
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031225043194-2042473617.png
1.2 0-1背包问题详情问题:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031225223004-572712551.png
建模与算法:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031225319401-216214884.png
1.3 双机调度问题详情问题:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031235755186-1319372016.png
建模与算法:
https://img2024.cnblogs.com/blog/3717086/202510/3717086-20251031235902921-810252851.png
[*]NP-hard问题小结:
[*]这样的问题有数千个,大量存在于各个应用领域
[*]至今没找到有效算法: 现有的算法的运行时间是输入规模的指数或更高阶函数
[*]至今没有人能够证明对于这类问题不存在多项式时间的算法
[*]从是否存在多项式时间算法的角度看,这些问题彼此是等价的,这些问题的难度处于可有效计算的边界
Algorithm + Data Structure = Programming
好的算法: 提高求解问题的效率&节省存储空间
算法的研究目标:
[*]问题 -> 建模并寻找算法
[*]算法 -> 算法的评价
[*]算法类 -> 问题复杂度估计
[*]问题类 -> 能够求解的边界
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101001249327-1133308691.png
计算复杂性理论的核心--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的输入实例的概率分布下,算法求解这些实例所需要的平均时间
计算公式
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101012319731-417504254.png
顺序检索算法问题实例https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101012625249-1801551868.png
最坏情况的时间估计:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101012825330-443909257.png
平均情况的时间估计:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101012931842-30151548.png
改进https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101013301332-1014142286.png
最坏时间复杂度: W(n) = n
平均时间复杂度: A(n) = n/2
1.5算法的伪码表示
1.关键字
[*]赋值语句: ←
[*]分支语句: if ... then ...
[*]循环语句: 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
运行实例:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101232009002-1586629375.png
改进的顺序检索输入: 数组 L, 元素从小到大排列,数x.输出: 若x在L中,输出x的位置下标j;否则输出0
伪码表示:
[*]j ← 1
[*]while j0 and x < A do
[*]A ← A
[*]i ← i-1
[*]A ← x
运行实例:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251101233054738-2002826821.png
二分归并排序MergeSort(A,p,r)输入: 数组A
输出: 按递增顺序排序的数组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符号https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000224100-2003166729.png
例子:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000343230-2022463919.png
大Ω符号https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000421456-1103046301.png
例子:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000448563-1081709295.png
小o符号https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000553922-615420824.png
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000643164-2054638420.png
小ω符号https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000741154-1561956622.png
例子:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000801120-634639752.png
大Θ符号https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102000849545-1004383768.png
2.小结:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102001358715-1565682199.png
1.7有关函数渐进的界的定理
1.设函数f、g、h的定义域为自然数集合
定理
[*]定理一
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102002328671-1018897851.png
估计函数的阶:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102002512039-660924429.png
[*]定理二: 函数的阶之间的关系具有传递性
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102002614341-1484985208.png
阶排序:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102002700382-619705808.png
[*]定理三
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102002734286-838167232.png
2.小结:
[*]估计函数的阶的方法: 计算极限
[*]阶具有传递性
[*]对数函数的阶低于幂函数的阶,多项式函数的阶低于指数函数的阶
[*]算法的时间复杂度是各步操作时间之和,在常数步的情况下取最高阶的函数即可
1.8几类重要的函数及性质
基本函数类: 阶的高低
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102005931219-1842300124.png
函数对数函数简化符号:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011208743-971877295.png
性质:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011259524-1702410582.png
指数函数与阶乘https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011443134-588775292.png
取整函数定义:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011550948-1181357474.png
实例:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011622781-1739066485.png
应用: 二分检索
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011703343-799484400.png
性质:
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011742642-248598788.png
证明性质(1):
https://img2024.cnblogs.com/blog/3717086/202511/3717086-20251102011847563-170187243.png
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 很好很强大我过来先占个楼 待编辑 东西不错很实用谢谢分享 谢谢楼主提供！ 懂技术并乐意极积无私分享的人越来越少。珍惜 谢谢分享，试用一下 用心讨论，共获提升！ 这个有用。 谢谢分享，试用一下 懂技术并乐意极积无私分享的人越来越少。珍惜 感谢分享，下载保存了，貌似很强大 前排留名，哈哈哈 感谢分享，下载保存了，貌似很强大 分享、互助 让互联网精神温暖你我 这个好，看起来很实用 不错，里面软件多更新就更好了 这个好，看起来很实用 感谢发布原创作品，程序园因你更精彩 感谢发布原创作品，程序园因你更精彩 热心回复！
页:
[1]
2