演算法時間復雜度

A. 什麼是演算法的時間復雜度

時間復雜度表面的意思就是代碼花費的時間，但是一般使用這個概念的時候，更注重的是隨著數據量增長，代碼執行時間的增長情況。一般認為一個基本的運算為一次運行算，例如加減乘除判斷等等
例1和例2時間復雜度都可以簡單認為是o(N)，一般用時間復雜度的時候要取一個下限即可，不用那麼精確，可能你認為例1是o(2N)而例2是o(n)，但實際上這兩者對於時間復雜度的作用來說沒區別，前面已經說了，時間復雜度關注的是數據量的增長導致的時間增長情況，o(2N)和o(n)在數據量增加一倍的時候，時間開銷都是增加一倍（線性增長）。

又例如兩重循環的時間復雜度是o(N的平方)，N擴大一倍，時間復雜度就擴大4倍。所以時間復雜度主要是研究增長的問題，一般效率較好的演算法要控制在o(N)或者o(log2N)

B. 如何計算一個演算法的時間復雜度

求解演算法的時間復雜度的具體步驟是：

1、找出演算法中的基本語句：

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

2、計算基本語句的執行次數的數量級：

（1）只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。

（2）這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

3、用大Ο記號表示演算法的時間性能：

（1）將基本語句執行次數的數量級放入大Ο記號中。

（2）如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：

for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;

（3）第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。

C. 演算法的時間復雜性是指（ ）。

演算法的復雜度分時間復雜度和空間復雜度。
時間復雜度：在運行演算法時所耗費的時間為f(n)(即 n的函數)。
空間復雜度：實現演算法所佔用的空間為g(n)（也為n的函數）。

D. 演算法的時間復雜度

分情況:
n=2^k;
i從1到n,則需要計算k+1次也就是log(n)+1.
n不等於2的某次方則恰好少計算一次..
計算次數為log(n).
平均復雜度O(log(n))

E. Dijkstra演算法時間復雜度

我們可以用大O符號將Dijkstra演算法的運行時間表示為邊數m和頂點數n的函數。

Dijkstra演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q,所以搜索Q中最小元素的運算(Extract-Min(Q))只需要線性搜索Q中的所有元素。這樣的話演算法的運行時間是O(n2)。

對於邊數少於n2稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra演算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點(Extract-Min)。當用到二叉堆的時候，演算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓演算法運行時間達到O(m + n log n)。相關問題和演算法

在Dijkstra演算法的基礎上作一些改動，可以擴展其功能。例如，有時希望在求得最短路徑的基礎上再列出一些次短的路徑。為此，可先在原圖上計算出最短路徑，然後從圖中刪去該路徑中的某一條邊，在餘下的子圖中重新計算最短路徑。對於原最短路徑中的每一條邊，均可求得一條刪去該邊後子圖的最短路徑，這些路徑經排序後即為原圖的一系列次短路徑。

OSPF（open shortest path first, 開放最短路徑優先）演算法是Dijkstra演算法在網路路由中的一個具體實現。
與Dijkstra演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。

與最短路徑問題有關的一個問題是旅行商問題(traveling salesman problem)，它要求找出通過所有頂點恰好一次且最終回到源點的最短路徑。該問題是NP難的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間演算法。

如果有已知信息可用來估計某一點到目標點的距離，則可改用A*演算法，以減小最短路徑的搜索范圍。

F. 演算法時間復雜度有幾種

演算法時間復雜度有3種：

1、常數階O(1),對數階O(log2n)(以2為底n的對數，下同),線性階O(n),

2、線性對數階O(nlog2n),平方階O(n^2)，立方階O(n^3),...，

3、k次方階O(n^k),指數階O(2^n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

(6)演算法時間復雜度擴展閱讀：

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),存在一個正常數c使得fn*c>=T(n)恆成立。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

在各種不同演算法中，若演算法中語句執行次數為一個常數，則時間復雜度為O(1),另外，在時間頻度不相同時，時間復雜度有可能相同，如T(n)=n^2+3n+4與T(n)=4n^2+2n+1它們的頻度不同，但時間復雜度相同，都為O(n^2)。

G. A*演算法的時間復雜度是多少

從數學上定義，給定演算法A，如果存在函數F(n)，當n=k時，F(k)表示演算法A在輸入規模為k的情況下的運行時間，則稱F(n)為演算法A的時間復雜度。這里首先要明確輸入規模的概念。關於輸入規模，不是很好下定義，非嚴格的講，輸入規模是指演算法A所接受輸入的自然獨立體的大小。例如，對於排序演算法來說，輸入規模一般就是待排序元素的個數，而對於求兩個同型方陣乘積的演算法，輸入規模可以看作是單個方陣的維數。為了簡單起見，總是假設演算法的輸入規模是用大於零的整數表示的，即n=1,2,3,……,k,…… 對於同一個演算法，每次執行的時間不僅取決於輸入規模，還取決於輸入的特性和具體的硬體環境在某次執行時的狀態。所以想要得到一個統一精確的F(n)是不可能的。為了解決這個問題，做以下兩個說明： 1.忽略硬體及環境因素，假設每次執行時硬體條件和環境條件是完全一致的。 2.對於輸入特性的差異，將從數學上進行精確分析並帶入函數解析式。

H. 演算法的時間復雜性

1 就是for(int i=1;i<=n;i++)，n+1中的1是判斷跳出。這就有點摳細節了說老實話。
2 學過時間復雜度沒有？不想解釋。

I. 演算法的時間復雜度

時間復雜度的表示: O(執行次數)

一個有序的元素列表查找某個元素可以用二分查找，每次取中間元素進行比較大小，直到相等。因為每次不符合時總會排除一半的元素 ，所以查找的次數為log2n，那麼時間復雜度為O(log2n)。如果是一個無序的元素列表，查找從位置0開始，那麼簡單查找的次數為n，那麼時間復雜度為O(n)。

除此之外快速排序為O(n*log2n)，選擇排序為O(n*n)。

旅行演算法就是n個旅行地點，你可從某個地方出發到餘下某下一個地點，走完所有地點。從最開始時走有n個地點可以選擇，接下來再走就有n-1個地點可以選擇，這樣直到只有一個地點可以選擇。那麼所有你可走的路徑就是一個階乘，選擇復雜度為O( n!)。

關於數組和鏈表的操作。先說數組，因為你有了元素的索引，可以隨機訪問，你就能快速找到這個元素，而且所有元素的讀取都是一樣的步驟，所以讀取時間復雜度為O(1)，數組的插入和刪除的時間復雜度為O(n)，因為要移動元素。鏈表的特性是每個都存儲了下一個元素的地址，只能順序訪問。那麼讀取插入刪除的時間復雜度分別是O(n)、O(1)、O(1)。

J. 如何計算一個演算法的時間復雜度

求解演算法的時間復雜度的具體步驟是：

1、找出演算法中的基本語句：

演算法中執行次數最多的那條語句就是基本語句，通常是最內層循環的循環體。

2、計算基本語句的執行次數的數量級：

（1）只需計算基本語句執行次數的數量級，這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可，可以忽略所有低次冪和最高次冪的系數。

（2）這樣能夠簡化演算法分析，並且使注意力集中在最重要的一點上：增長率。

3、用大Ο記號表示演算法的時間性能：

（1）將基本語句執行次數的數量級放入大Ο記號中。

（2）如果演算法中包含嵌套的循環，則基本語句通常是最內層的循環體，如果演算法中包含並列的循環，則將並列循環的時間復雜度相加。例如：

for(i=1;i<=n;i++)x++;for(i=1;i<=n;i++)
for(j=1;j<=n;j++)x++;

（3）第一個for循環的時間復雜度為Ο(n)，第二個for循環的時間復雜度為Ο(n2)，則整個演算法的時間復雜度為Ο(n+n2)=Ο(n2)。