标签：归纳 多项式 第一章 问题 N0 算法 NP 排序
- 输入：有零个或者多个输入
- 输出：至少有一个输出
- 确定行：组成算法的每条指令清晰、无歧义
- 有限性：算法中每条指令的执行次数有限。执行每条指令的时间也有限
- 自然语言：通俗易懂，但缺乏直观性和简洁性，且易产生歧义。
- 程序流程图：描述算法形象、直观，容易理解，绘制过程比较费时费力，难以修改。
- 伪代码：简单易懂，修改容易，易于转化为程序语言代码，但伪代码格式难以规范。
- O的定义：如果存在正的常数C和自然数N0，使得当N > =N0时有f(N) <=Cg(N)，则称函数f(N)当N充分大时上有界，且g(N)是它的一个上界，记为f(N)=O(g(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)同阶
- o的定义：对于任意给定的ε＞0，都存在正整数N0，使得当N > =N0时有f(N)/Cg(N) <= ε,则称函数f(N)当N充分大时的阶比g(N)低，记为f(N)=o(g(N))。
- O(1): 表示算法的运行时间为常量时间
- O(logn): 二分查找等算法
- O(n): 线性算法，例如线性查找
- O(nlogn): 快速排序、归并排序等算法
- O(n2): 对数组进行排序的简单算法，例如冒泡排序等
- O(n3): 做两个n阶矩阵的乘法运算
- O(2n): 求具有n个元素集合的所有子集的算法
- O(n!): 求具有n个元素的全排列的算法
-
P问题：这里P指代Polynomial。P问题是指能够在多项式时间内解决的问题，这意味着计算机能够在有限时间内完成计算。整数排序问题就是P问题，不管你是采用冒泡排序还是快速排序，也无论你是对于10个整数排序还是10亿个整数排序。
-
NP问题：NP指的是(Nondeterministic Polynomial)，即非确定性多项式时间。NP问题是指我们能够在多项式时间内验证一个解的问题。
- P问题与NP问题的关系：对于一个问题，如果我们能够在多项式时间内解决，那么我们肯定也能在多项式时间内验证某个猜测是否为这个问题的一个解，因此P问题也属于NP问题，或者说P问题是NP问题的一个子集。
- NP完全问题：所有P问题都可以约归到NP完全问题
标签：归纳,
多项式,
第一章,
问题,
N0,
算法,
NP,
排序
From： https://www.cnblogs.com/xiaoqv3355/p/16985711.html