什么是時(shí)間復(fù)雜度
時(shí)間復(fù)雜度:
算法的時(shí)間復(fù)雜度是一個(gè)函數(shù),它定量的描述了該算法的運(yùn)行時(shí)間.
最壞時(shí)間復(fù)雜度:
相同大小的不同輸入值可能造成算法的運(yùn)行時(shí)間不同,因此我們通常使用算法的最壞復(fù)雜度,記做T(n),即任何大小 n所需的最大運(yùn)行時(shí)間
舉例來說,有著T(n)=O(n)的算法被稱作線性時(shí)間算法,而 T(n) = O(M^n) 和 M^n= O(T(n)) 的算法被稱作指數(shù)時(shí)間算法
由于計(jì)算機(jī)使用二進(jìn)制的記數(shù)系統(tǒng)，對(duì)數(shù)常常以2為底（即log2
n樊破，有時(shí)寫作lg n）
常數(shù)時(shí)間：O(n)
對(duì)數(shù)時(shí)間：O(log(n)), 二分搜索
線性對(duì)數(shù)時(shí)間：O(nlog(n)), 最快的比較排序
二次時(shí)間： O(n^2), 冒泡排序、插入排序
常見排序算法的時(shí)間復(fù)雜度：
image.png
