算法分析--时间复杂度

1. 声明

内容是我抄得别人的，自己拿来做笔记看一下。

2. 复杂度记号

$O$: 大O符号，也是最常用的，它表示的是小于等于，上界，也就是最差情况下的时间复杂度。
$\Omega$: 大欧米伽，它表示的是大于等于，下界，也就是最好情况下的时间复杂度。
$\Theta$: 大西塔，它表示的是确界，就是等于。
$o$: 小O符号，表示小于。
$\omega$: 小omega,表示大于。

抄了三个数学定义

第一个是渐进上界
$$\begin{gathered} f(n)=O(g(n)):=\exists c,n,n_0\in N_{+},n>n_0,\forall f(n),s.t. \\ 0\le f(n)\le cg(n) \end{gathered}$$
第二个是渐进下界
$$\begin{gathered} f(n)=\Omega (g(n)):=\exists c,n,n_0\in N_{+},n>n_0,\forall f(n),s.t. \\ 0\le cg(n)\le f(n) \end{gathered}$$
第三个是渐进等价
$$\begin{gathered} f(n)=\Theta (g(n)):=\exists c_0,c_1,n,n_0,n>n_0,\forall f(n),s.t. \\ {c}_{1}g(n)\le f(n)\le c_{2}g(n) \end{gathered}$$

3. P问题、NP问题、NPC问题、NP-hard问题

强烈推荐看下matrix67的这篇文章，好多人都是抄的这篇文章。

我这里只简单写下自己的理解。

首先这个英文字母是polunomial的缩写，是多项式的意思。

而多项式其实就是${\sum }_{i=0}^k{a}_i{x}^i$。

P具体是什么的缩写不太清楚了，但意思是未确定的。

• P问题：能在多项式时间复杂度内解决的问题。
• NP问题：能在多项式时间内验证是否正确的问题。
• NP完全问题：NP问题中最终归约到的问题。
• NP-hard问题：NP问题最终归约到的问题，但并不一定是NP问题

原文

时间复杂度
matrix67