演算法復雜度

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

如果一個問題的規模是n，解決這一問題所需演算法所需要的時間是n的一個函數T(n)，則T(n)稱為這一演算法的時間復雜度。

⑵ 演算法的時間復雜度是指什麼

就是對演算法執行時所花時間的度量。一般為問題規模的函數。

計算機科學中，演算法的時間復雜度是一個函數，它定量描述了該演算法的運行時間。這是一個關於代表演算法輸入值的字元串的長度的函數。時間復雜度常用大O符號表述，不包括這個函數的低階項和首項系數。使用這種方式時，時間復雜度可被稱為是漸近的，它考察當輸入值大小趨近無窮時的情況。

演算法復雜度分為時間復雜度和空間復雜度。其作用： 時間復雜度是指執行演算法所需要的計算工作量；而空間復雜度是指執行這個演算法所需要的內存空間。演算法的復雜性體現在運行該演算法時的計算機所需資源的多少上，計算機資源最重要的是時間和空間資源，因此復雜度分為時間和空間復雜度。

相關內容解釋：

函數在數學上的定義：給定一個非空的數集A,對A施加對應法則f,記作f（A）,得到另一數集B,也就是B=f（A）。那麼這個關系式就叫函數關系式,簡稱函數。

簡單來講，對於兩個變數x和y，如果每給定x的一個值，y都有唯一一個確定的值與其對應，那麼我們就說y是x的函數。其中，x叫做自變數，y叫做因變數。

⑶ 演算法時間復雜度有幾種

演算法時間復雜度有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的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

(3)演算法復雜度擴展閱讀：

一般情況下，演算法中基本操作重復執行的次數是問題規模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)。

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

是說明一個程序根據其數據n的規模大小 所使用的大致時間和空間
說白了 就是表示 如果隨著n的增長 時間或空間會以什麼樣的方式進行增長

例
for(int i = 0; i < n;++i)
;
這個循環執行n次 所以時間復雜度是O(n)

for(int i = 0; i< n;++i)
{
for(int j = 0; j< n;++j)
;
}
這嵌套的兩個循環 而且都執行n次
那麼它的時間復雜度就是 O(n^2)

時間復雜度只能大概的表示所用的時間
而一些基本步驟 所運行的時間不同 我們無法計算 所以省略
如

for(int i = 0;i < n;++i)
a = b;
和
for(int i = 0;i < n;++i)
;
這個運行的時間當然是第二個快 但是他們的時間復雜度都是 O(n)
判斷時間復雜度看循環

⑸ 演算法的時間復雜度

空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。
我們一般所討論的是除正常佔用內存開銷外的輔助存儲單元規模.

本人: 空間復雜度跟指令條數沒有必然聯系,同一種演算法你可以寫得很長 也可以寫得很短 但是他們的復雜度是一樣的

⑹ 演算法的時間復雜度是指什麼具體點

演算法復雜度不是簡單的時間的度量
是用來評價演算法優劣程度的依據
比如，一個程序要掃描100 * n * n + 10000 * n + 99999遍，那麼時間復雜度是O(n^2)
也就是說，時間復雜度只取次數最高的項，並且忽略系數

所以，時間復雜度是用來描述隨著 n 的增大，演算法耗時「增大」的！不是用來描述運行所花時間的（這個我們初中老師給我們強調了半天）

還有一點，O(9999999999)（實際應寫為O(1),這里只是表達意思）和O(n)的演算法那個好？
答案是O(9999999999)，因為他的耗時不隨n的增大而變化，所以他更優
一般來說，演算法的好壞是這樣的 （>表示好於) O(1) > O(logn) > O(n) > O(n logn) > O(n^2) > O(n^3) > O(2^n) > O(n!)

⑺ 如何估算演算法的復雜度

就是根據程序運行的最基本的操作的次數，記為t（n）
例：演算法：
for（i=1;i<=n;++i）
{
for(j=1;j<=n;++j)
{
c[
i
][
j
]=0;
//該步驟屬於基本操作
執行次數：n的平方
次
for(k=1;k<=n;++k)
c[
i
][
j
]+=a[
i
][
k
]*b[
k
][
j
];
//該步驟屬於基本操作
執行次數：n的三次方
次
}
}
則有
t（n）=
n的平方+n的三次方，根據上面括弧里的同數量級，我們可以確定
n的三次方
為t（n）的同數量級
則有f（n）=
n的三次方，然後根據t（n）/f（n）求極限可得到常數c
則該演算法的
時間復雜度：t（n）=o（n^3）
註：n^3即是n的3次方。

⑻ 演算法復雜度是什麼概念

同一問題可用不同演算法解決，而一個演算法的質量優劣將影響到演算法乃至程序的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間復雜度和空間復雜度來考慮。

1、時間復雜度

（1）時間頻度
一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機運行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數多，它花費時間就多。一個演算法中的語句執行次數稱為語句頻度或時間頻度。記為T(n)。

（2）時間復雜度
在剛才提到的時間頻度中，n稱為問題的規模，當n不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間復雜度概念。

一般情況下，演算法中基本操作重復執行的次數是問題規模n的某個函數，用T(n)表示，若有某個輔助函數f(n),使得當n趨近於無窮大時，T（n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n)),稱O(f(n)) 為演算法的漸進時間復雜度，簡稱時間復雜度。

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

按數量級遞增排列，常見的時間復雜度有：
常數階O(1),對數階O(log2n),線性階O(n),
線性對數階O(nlog2n),平方階O(n2)，立方階O(n3),...，
k次方階O(nk),指數階O(2n)。隨著問題規模n的不斷增大，上述時間復雜度不斷增大，演算法的執行效率越低。

2、空間復雜度
與時間復雜度類似，空間復雜度是指演算法在計算機內執行時所需存儲空間的度量。記作:
S(n)=O(f(n))

說到底,就是程序執行效率和佔用空間的問題.

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

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

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)。

⑽ 演算法的時間復雜度

時間復雜度的表示: 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)。