一、算法概述:
1、算法的定义:算法是解决问题的一种方法或者一个过程。
算法是求解特定问题的步骤的一种描述:(1)输入:有外部提供的量作为输入(2)输出:至少有一个输出(3)确定性:算法的每条指令无歧义(4)有限性:算法的执行时间、执行次数有限
2、程序的定义:程序是算法利用程序设计语言的具体实现,可以不满足有限性
3、算法设计的步骤:理解问题→精确问题的解或者近似解选择数据结构→设计算法→证明正确性→分析算法→设计程序
4、np完全理论:一般来说,可在多项式时间内解决的问题为易解问题,要用超多项式时间解决的问题为难解问题
5、(1)p问题:是一类可以利用确定的算法在多项式时间内求解的判定问题
(2)np问题:所有非确定多项式时间可解的判定问题
(3)多项式时间非确定性算法:算法的验证可在多项式时间内完成的算法
二、关于计算:
1、算法的时间复杂度可以这样表示:原式=O(上限值);
2、Ω(g(n))代表g比f小;O(g(n))代表g比f大;SEI它代表一样
3、最大的是n!,之后是指数函数;1/n看成是1(因为是考虑的无限大的情况下)
标签:总结,有限性,多项式,第一章,问题,算法,时间,np From: https://www.cnblogs.com/Sakuras628/p/16989484.html