⑴ 演算法的時間復雜度是指什麼
演算法的時間復雜度是指該演算法舉虛枯所需要的計算工作量隨問題規模增加而增加的趨勢,也就是演算法的運行時間與問題規模之間的關系。
1、演算法時間復雜度的概念
演算法時間復雜度是指在分析演算法性能時,關注的是該演算法的計算復雜程度。主要是根據演算法中基本操作的執行次數來估算演算法的效率。演算法的時間復雜度在一定程度上衡量了演算法的好壞,是在進行演算法性能分析時的一項基本指標。
2、計算時間復雜度的方法
通過代碼分析可以得出一個演算法的時間復雜度,一般採用大O表示法。大O表示法是一種用於描述演算法復雜度的表示方法。
用一個大O符號加上一個括弧括起來的函數描述演算法復雜度,在大O符號後面的函數里,n表示數據輸入的總量,T(n)表示演算法執行所需的時間復雜度函數。
5、總結:
演算法的時間復雜度是分析演算法效率的一種常用指標,可以通過大O記號表示演算法需要執行的操作次數,常見類型包括常數時間復雜度、線性時間復雜度、對數時間復雜度、平方時間復雜度和指數時間復雜度。
在實際應用中,需要根據具體需求綜合考慮時間復雜度和空間復雜度。
⑵ 大O表示法
表示時間的大O符號,是用來描述演算法效率的語言和度量單位。
大O表示法分析了演算法的運行時間如何隨列表的增長而增長,指出了演算法最糟情況下的運行時間。
n為列表的長度,(n)作為大O表示法的操作數。
大O表示法通常不考慮常量,因為如果這兩種演算法的大O運行時間不同,這個常量將無關要緊。
大O表示法不考慮乘以、除以、加上或減去的數字。如O(n+26)、O(n-26)、O(n*26)、O(n/26),它們都應該表示為O(n)。
如下圖:
其中Ο(log2n )、Ο(n)、 Ο(nlog2n )、Ο(n2)和Ο(n3)稱為多項式時間,而Ο( 2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者(即多項式時間復雜度的演算法)是有效演算法,把這類問題稱為P(Polynomial,多項式)類問題,而把後者(即指數時間復雜度的演算法)稱為NP(Non-Deterministic Polynomial,非確定多項式)問題。
1、《演算法圖解》 https://www.manning.com/books/grokking-algorithms
2、《演算法的基本概念》 https://www.zybuluo.com/defias/note/286416