计算机算法设计与分析第一章总结
2022/9/5 14:22:55
本文主要是介绍计算机算法设计与分析第一章总结,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1.1算法与程序
算法的性质:输入、输出、确定性、有限性。
程序是算法用某种程序设计语言的具体实现,可以不满足算法的有限性。
1.2算法复杂性分析
算法复杂性是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要空间资源的量称为空间复杂性。
一般只讨论时间复杂性。
实践表明,可操作性性最好的是最坏情况下的时间复杂性。
分析时间复杂性时可以将复杂性函数简化为渐进复杂性,比较两个算法的渐进复杂性的阶即可确定哪个算法的效率高。
上界(O):如果存在正的常数C和自然数N0 ,使得当N >= N0时有f(N) <= Cg(N),则称函数f(N)当N充分大时上有界,且g(n)是它的一个上界,记为f(N) = Og(N)。这时还说f(N)的阶不高于g(N)的阶。
下界(Ω):如果存在正的常数C和自然数N0 ,使得当N >= N0时有f(N) >= Cg(N),则称函数f(N)当N充分大时下有界,且g(n)是它的一个下界,记为f(N) = Ωg(N)。这时还说f(N)的阶不低于g(N)的阶。
定义f(N) = θ(g,(N))当且仅当f(N) = O(g(N))且f(N) = Ω(g(N))是,称为f(N)与g(N)同阶。
如果对于任意给定的ε>0,都存在正整数N0,使得当N >= N0时有f(N) / g(N) < ε,则称函数f(N)当N充分大时的阶比g(N)低,记为f(N) = o(g(N))。
1.3NP完全性理论
1.P类问题:存在多项式时间算法的问题。
2.NP问题:能在多项式时间内验证得出一个正确解的问题。
3.NPC类问题:存在这样一个NP问题,所有的NP问题都可以约化成它。
4.NP-Hard问题:NP-Hard问题是这样一种问题,它满足NPC问题定义的第二条但不一定要满足第一条(就是说,NP-Hard问题要比 NPC问题的范围广,NP-Hard问题没有限定属于NP),即所有的NP问题都能约化到它,但是它不一定是一个NP问题。
P⊆NP 并且 NPC = NP ∩ NP-hard
这篇关于计算机算法设计与分析第一章总结的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?