上課筆記，原文書:
Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang
3.1 Models for computation
待補
3.1.1 Turing machines
待補
3.1.2 Circuits
待補
3.2 The analysis of computational problems
3.2.1 How to quantify computational resources
- $f(n)$ is $O(g(n))~\Rightarrow~\exists~c>0, n_0>0, ~\text{s.t.}~ 0 < f(n) \le cg(n), \forall n>n_0$
- $f(n)$ is $\Omega(g(n))~\Rightarrow~\exists~c>0, n_0>0, ~\text{s.t.}~ 0 < cg(n)\le f(n), \forall n>n_0$
- $f(n)$ is $\Theta(g(n))~\Rightarrow~\exists~c_1>0, c_2>0, n_0>0, ~\text{s.t.}~ 0 < c_1g(n)\le f(n)\le c_2g(n), \forall n>n_0$
- $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$
3.2.2 Computational complexity
待補
3.2.3 Decision problems and the complexity classes $\mathbf{P}$ and $\mathbf{NP}$
待補
3.2.4 A plethora of complexity classes
待補
3.2.5 Energy and computation
待補
3.3 Perspectives on computer science
待補
