---
title: 複雜度
description: 評估時間複雜度與複雜度定義和證明
tags: 演算法基礎
robots: noindex, nofollow
langs: zh
---
複雜度
===
複雜度可以用以評估算法使用的空間與時間隨*輸入值*的變化而增長的幅度，這可以使得我們判斷一個算法可否解決當前的問題。

複雜度以大O符號表示
## 常見的複雜度
1. 常數複雜度(constant complexity) $O(1)$
2. 對數複雜度(logorithmatic complexity) $O(\log(n))$
3. 線性複雜度(linear comlexity) $O(n)$
4. 線性對數複雜度(linearithmic time) $O(n\log(n))$
5. 二次/三次複雜度 $O(n^2)$ $O(n^3)$

## 推導
若說一個函數$f(x)$滿足複雜度$O(y=g(x))$
則 $\begin{split}
\lim_{x->\infty} \frac{f(x)}{y}
\end{split}$存在且收斂於定值, $\begin{split}
\lim_{x->\infty} \frac{f(x)}{g(x)}=k,\; k\in R
\end{split}$

好比說若今天$f(x)=x(x-1)=x^2-x$
我們說他滿足$O(x^2)$
則$\begin{split}
\lim_{x->\infty} \frac{f(x)}{x^2} = \lim_{x->\infty} \frac{x^2-x}{x^2} = 1
\end{split}$
收斂於1
所以我們說$f(x)$滿足$O(x^2)$
> 註解:
> 整理時
> $\begin{split}\lim_{x->\infty} \frac{x^2-x}{x^2} = \lim_{x->\infty} \frac{x^2}{x^2} - \lim_{x->\infty} \frac{x}{x^2}\end{split}$
> 因$\begin{split}\lim_{x->\infty}\frac{x^2}{x^2}=1\end{split}$
> 而$\begin{split}\lim_{x->\infty}\frac{x}{x^2}=0\end{split}$
> 故$\begin{split}\lim_{x->\infty} \frac{x^2-x}{x^2} = 1\end{split}$

而由此可知$f(x)$不滿足$O(x)$
但可滿足$O(x^3)$、$O(x^4)$以及更高次的複雜度
也由此可知複雜度表示的是一個上限(比如說滿足$O(x^3)$的集合完全包含滿足$O(x^2)$的集合)

## 評估
以經驗談而言，多數的測機約可在1秒的時間限制中跑$10^7$~$10^8$個指令(instruction)，意指將題目的輸入限制代入得出的時間複雜度後，得到的數字小於這個區間，就代表基本上這個算法的效率足以解決當前的問題

而空間複雜度評估時相對簡單得多，就不多家贅述(加上空間複雜度爆掉之前你的時間複雜度常常會先爆XD)