陣列演算法複雜度分析,效率。演算法複雜度是什麼概念?

時間 2023-01-16 21:00:13

1樓:網友

關於演算法複雜度的問題,是通過演算法的步數,和時間還有一個就是記憶體的佔用還有就是程式轉換成機器語言時的大小!

時間你這個是不太好表示了!因為程式太小!

但步數是可以表示的!你可以在程式中間加一個變數記錄他的執行次數!但有時會步數一樣多!這時就要看他的記憶體佔用啊!語句長短啊!

綜合以上。你這個是第一個效率高!

2樓:匿名使用者

第一個是從一端開始賦值,判斷n次,賦值n次;時間複雜度o(n);

第二個是兩端同時開始賦值,判斷n/2次,賦值n次,時間複雜度也是o(n);

這麼列出來以後,你也看的出來,後者效率更高,因為是每次判斷後執行兩句賦值,使判斷的次數少了一半。

3樓:網友

是第二組效率高,我是群裡的那位,採納我的答案吧。

演算法複雜度是什麼概念?

4樓:江湖三腳貓

看下資料結構,簡單解釋下:

演算法複雜度包括時間複雜度和空間複雜度。

時間複雜度就是執行演算法所需要的時間(執行多少次賦值、比較、判斷等操作),空間複雜度就是執行該演算法需要消耗多少儲存空間。

2者都是越低越好,但往往不能兼顧,需要找到時間和空間複雜度的平衡點。

如何對一個程式進行演算法分析?時間複雜度怎麼算?

5樓:匿名使用者

演算法的複雜性。

演算法的複雜性是演算法效率的度量,是評價演算法優劣的重要依據。一個演算法的複雜性的高低體現在執行該演算法所需要的計算機資源的多少上面,所需的資源越多,我們就說該演算法的複雜性越高;反之,所需的資源越低,則該演算法的複雜性越低。

計算機的資源,最重要的是時間和空間(即儲存器)資源。因而,演算法的複雜性有時間複雜性和空間複雜性之分。

不言而喻,對於任意給定的問題,設計出複雜性儘可能低的演算法是我們在設計演算法時追求的一個重要目標;另一方面,當給定的問題已有多種演算法時,選擇其中複雜性最低者,是我們在選用演算法適應遵循的一個重要準則。因此,演算法的複雜性分析對演算法的設計或選用有著重要的指導意義和實用價值。

簡言之,在演算法學習過程中,我們必須首先學會對演算法的分析,以確定或判斷演算法的優劣。

1.時間複雜性:

例1:設一程式段如下(為討論方便,每行前加一行號)

(1) for i:=1 to n do

(2) for j:=1 to n do

(3) x:=x+1

試問在程式執行中各步執行的次數各為多少?

解答:行號 次數(頻度)

(1) n+1

(2) n*(n+1)

(3) n*n

可見,這段程式總的執行次數是:f(n)=2n2+2n+1。在這裡,n可以表示問題的規模,當n趨向無窮大時,如果 f(n)的值很小,則演算法優。

作為初學者,我們可以用f(n)的數量級o來粗略地判斷演算法的時間複雜性,如上例中的時間複雜性可粗略地表示為t(n)=o(n2)。

2.空間複雜性:

例2:將一一維陣列的資料(n個)逆序存放到原陣列中,下面是實現該問題的兩種演算法:

演算法1:for i:=1 to n do

b[i]:=a[n-i+1];

for i:=1 to n do

a[i]:=b[i];

演算法2:for i:=1 to n div 2 do

begint:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t

end;演算法1的時間複雜度為2n,空間複雜度為2n

演算法2的時間複雜度為3*n/2,空間複雜度為n+1

顯然演算法2比演算法1優,這兩種演算法的空間複雜度可粗略地表示為s(n)=o(n)

資訊學比賽中,經常是:只要不超過記憶體,儘可能用空間換時間。

演算法複雜度的比較 第五題,為什麼f和g同階?

6樓:網友

用換底公式。。loga b = logc b / logc a。。

所有log不管底是多少,換完之後都只差一個常數,都是同階。。。

7樓:匿名使用者

**清楚點 看不清 左邊那個n的上面是個常數嗎。

log2 n^k =klog2 n

因為k為常數所以log2 n與klog2 n 同階。

運用分而治之 (divied and conquer) 設計一個演算法找出陣列中最大值的位置,並分析其時間複雜度。

8樓:我是百人敵

mymax(int a, int start, int end)其中max(a,b)返回a,b較大者。

複雜度為o(n/2)

演算法時間複雜度怎麼算

在一個長度為n的陣列中插入一個元素的演算法複雜度是多少?麻煩高手指點。謝謝:)

9樓:匿名使用者

n/2就是o(n)啊,呵呵。計算方式就是這樣的,如果有一個n,那就是n,即存在一個k,k只要是常數k,那麼kn的時間複雜度就是o(n),如果有兩個n,那就是o(n^2)了。

兩個陣列比較(演算法) 怎樣算最優化!麻煩告訴我

10樓:雨之槐

其實可以優化一下:

1 為每個物件定義雜湊演算法,2 把每個陣列按雜湊值排序,3 從頭到尾比較陣列的元素。

排序時間複雜度為o(,之後的遍歷過程時間複雜度就降到o(1)了。

時間複雜度相同的演算法一樣好嗎,氣泡排序演算法的時間複雜度是什麼

大二的猴 如果只分析你上面段程度,顯然方法二做了許多無用功,當然一好。時間複雜度估的是個時間隨規模n增長的趨勢,他倆的趨勢是一樣的。給定規模n,如果方法二能跑,那方法一肯定能跑,只不過比前者多常數倍時間而已,你跑1秒,我不過跑2秒而已,你跑一天,我跑倆天而已,你要跑一年以上,那勸你還是找個更快的演算...

軟體設計中演算法複雜度中大O 的具體意思

同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間複雜度和空間複雜度來考慮。1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間,從理論上是不能算出來的,必須上機執行測試才能知道。但我們不可能...

求問個c語言問題 這個演算法的時間複雜度怎麼看

時間複雜度等於內層迴圈的值,不算外層的。內層是x那麼時間複雜度記為o 1000 如果是並列的,比如。x 0 y 0 while x 100 x while y 100 y 這個並列的就記為o 100 100 o 200 看它的迴圈語句,while語句會執行1000次。c語言演算法的時間複雜度如何計算...