1.1 O(order)的定义

• 如果存在正常数$C$和自然数N0，使得当$N\ge N_0$时有$f(N)\le Cg(N)$，则记
  $f(N)=O(g(N))$可以说：$f(N)$ 的阶不高于$g(N)$的阶。

1.2 $\Omega$与$\theta$定义

• $\Omega$：如果存在正常数$C$和自然数N0，使得当$N\ge N_0$时有$f(N)\ge Cg(N)$，
  则记$f(N)=\Omega (g(N))$
• $\theta$：如果$f(N)=O(g(N))$且$f(N)=\Omega (g(N))$，那么称为$f(N)$与$g(N)$同阶，
  则记$f(N)=\theta (g(N))$

1.3 练习

1. 证明$N^3\ne O(N^2)$（反证法）
   

2. 证明以下运算规则

   • $O(f)+O(g)=O(max(f,g))$

   

   • $O(f)+O(g)=O(f+g)$
     

   • $O(f)O(g)=O(fg)$
     

   • $O(Cf)=O(f)$
     

   • 如果 $g(n)=O(f(n))$ , 则$O(f(n))+O(g(n))=O(f(n))$
     

   • $f(n)=O(f(n))$
     

3. 假设某算法在输入规模为n时的计算时间为$T(n)=3\times 2n$。在某台计算机上实现并完成该算法的时间为 $t$ 秒。现有另一台计算机，其运行速度为第一台的 64 倍

   (1)那么在这台新机器上用同一算法在 $t$ 秒内能解输入规模多大的问题？

   • 解：设第一台计算机执行速度为$V$（次/秒），另一台计算机输入规模为$m$
     

   (2) 若上述算法的计算时间改进为$T(n)=n^2$，其余条件不变，则在新机器上用t秒时间能解输入规模多大的问题？

   • 解：
     

   (3)若上述算法的计算时间进一步改进为$T(n)=8$，其余条件不变，那么在新机器上用t秒时间能解输入规模多大的问题？

   • 解：
     

4. 硬件厂商XYZ公司宣称他们最新研制的微处理器运行速度与其竞争对手ABC公司同类产品的100倍。对于计算复杂性分别为$n$, $n^2$,$n^3$和$n!$的各算法，若用ABC公司的计算机能在1小时内能解输入规模为n的问题，那么用XYZ公司的在1小时内分别能解输入规模为多大的问题？

   • 解：
     

5. 证明$n!=o(n^n)$
   

本文笔记来自于上课记录笔记，以及闵老板笔记：https://blog.csdn.net/minfanphd/article/details/121242658