演算法的複雜度靠什麼來度量急需解答

2021-03-19 18:19:45 字數 2675 閱讀 3728

1樓:匿名使用者

演算法的高低體現在執行該演算法所需要計算機資源的多少,當需要的資源越多,我們就說該演算法的複雜性越高。

演算法的複雜度是以什麼來度量的?

2樓:匿名使用者

演算法執行過程中所需要的基本運算次數

3樓:肖詩柳尋群

一個演算法的複雜度評價主要從

時間複雜度

和空間複雜度

來考慮時間複雜度

在剛才提到的時間頻度中,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))

為演算法的漸進時間複雜度,簡稱時間複雜度。

空間複雜度

與時間複雜度類似,空間複雜度是指演算法在計算機內執行時所需儲存空間的度量。記作:

s(n)=o(f(n))

什麼是演算法的複雜性?如何度量?什麼是演算法漸進性態的階

4樓:匿名使用者

考慮演算法複雜性的漸進性態時,已知f(n)=2n*n+11n-10,則時間複雜性在漸進意義下的階為( b ) 。

a.o(n) b.o(n*n) c.o(2n*n) d.o(2n*n+11n-10)

2在一個長度為n的順序表的任一位置插入一個新元素的漸進時間複雜度為( a )。

a. o(n) b. o(n/2) c. o(1) d. o(n2)

這是前兩題的答案 如果是的話 那所有的十二題的答案就是這幾個了:

babda cdcdc ba 只是隱約記得 自己做的

演算法的效率一般用什麼來度量a時間複雜度b空間複雜度c執行的時間d佔用的時間

5樓:丁利娟

c 演算法效率是指演算法執行的時間,演算法執行時間需通過依據該演算法編制的程式在計算機上執行時所消耗的時間來度量。而度量一個程式的執行時間通常有兩種方法*(一)事後統計的方法(二)事前分析估算的方法。

演算法複雜度的意義是什麼?

6樓:匿名使用者

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

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

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

演算法的時間複雜度取決於什麼?

7樓:匿名使用者

我認為大多取決與問題的規模和演算法的優劣!

一般是計算迴圈的次數來覺得時間複雜度!

8樓:匿名使用者

從演算法中選取一種對於所研究的問題(或演算法型別)來說是基本操作的原操作,以基本操作重複執行的次數作為演算法時間複雜度的度量

9樓:嘟嘟嘟

輸出資料量,演算法的優劣,輸入資料量

10樓:匿名使用者

問題的規模,一般跟n有關呀。

11樓:許璞脫曜文

算選取種於所研究

問題(或算

型別)說

基本操作

原操作基本操作重複執行數作算

間複雜度度量

演算法的空間複雜度於時間複雜度的關係

有 必定 的話不對。因為對一些特殊情況存在特例有高的時空複雜度或同時為低的時空複雜度。但對一般情況下給定儲存空間如給定65535k的記憶體但不限定時間時,就存在時間空間的負相關關係。對於既不限定時間,也不限定空間的程式,演算法的時間複雜度和空間複雜度可以同時很大,也可以同時很小。如t n o n 且...

演算法的時間複雜度和空間複雜度怎麼算啊?(我看書上的按人家的思路能看通,但是給我我不會算)

原因是你沒看懂。找其他書參考下。網上說的肯定沒有書裡的具體全面。nothing replaces hard work.good luck 什麼是時間複雜度 空間複雜度?1 時間複雜度是指執行演算法所需要的計算工作量。時間複雜度是一個函式,它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的...

設計n個數的排序演算法,並要求計算演算法複雜度

氣泡排序的演算法時間複雜度上o n 2 氣泡排序是這樣實現的 首先將所有待排序的數字放入工作列表中。從列表的第一個數字到倒數第二個數字,逐個檢查 若某一位上的數字大於他的下一位,則將它與它的下一位交換。重複2號步驟,直至再也不能交換。氣泡排序的平均時間複雜度與插入排序相同,也是平方級的,但也是非常容...