1樓:匿名使用者
時間複雜度是不考慮首項係數和低階項的。
2樓:匿名使用者
我還沒開始學軟體,大一準新生,感覺好複雜...
快速排序方法的時間複雜度為o(n^2)=n(n-1)/2.
3樓:匿名使用者
1)對於你的問題簡單解釋如下:
理論計算機研究中,衡量演算法一般從兩個方面分析:時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的,下面簡單解釋一下時間複雜度:
對於一個資料規模為n的問題,解決該問題的演算法所用時間可以用含有n的函式t(n)來表示。對於絕大多數情況,我們只需要瞭解演算法的一般效能而不考慮細節,也就是說,我們只關心函式t(n)的表示式的形式,而不關心表示式的常數係數等與資料規模沒有關係的量值。對於函式t(n),我們又進一步將它簡化為o(n),即只考慮演算法平均執行時間的「瓶頸」,也就是t(n)表示式中,關於變數n增長最快的哪一項。
比如下面的**:
for(int i=1; i<=n*2; i++)for(int j=1; j<=n; j++)// do something here
那麼這個演算法的時間複雜度就是o(n^2),因為它有兩層迴圈,每層迴圈的資料規模都是n。注意第一層迴圈(外迴圈)要迭代n*2次,則實際上t(n)=2*n*n,而對於o(n)來說,我們忽略了常數2,只保留了n^2。這就是大o記法的一個概括,並不精確。
對於時間複雜度的更精確、深入的解釋,可以自己查閱《演算法導論》第一章。
2)更正你的問題:快速排序演算法的時間複雜度應該為o(n lg n)。注意三種時間複雜度符號表示的不同意義!
英文字母o代表的是平均執行時間,因此對於快速排序來說應該是o(n lg n)。而使用下界函式omega或者上界函式theta則分別表示演算法執行的最快和最慢時間。對於未使用隨機化的快速排序,理論上可以證明,存在某一方法構造出一組資料使快速排序「退化」成平方複雜度演算法即theta(n^2)。
但是對於其o(n)表示法應該為o(n^2)。
4樓:匿名使用者
n 趨於無窮大時無窮大的階數。
同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。
電腦科學中,演算法的時間複雜度是一個函式,它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。
使用這種方式時,時間複雜度可被稱為是漸近的,它考察當輸入值大小趨近無窮時的情況。
時間複雜度為n(n-1)/2時記作o(n^2),還是什麼意思,為什麼這兩個會相等?
5樓:匿名使用者
g(x)記作o(f(x))的含義是存在一個正數c,使得g(x) < c*f(x),上面如果令c=1,那麼,對於任何n,n(n-1)/2 <= n^2都是成立的。
6樓:匿名使用者
當n趨於無窮大時可忽略常數,所以-1,/2可忽略,答案是o(n^2)
7樓:宇飛天才小諸葛
當n——>無窮,n(n-1)/2=n^2/2-n/2——>n^2(n/2的影響忽略不計。)
8樓:藍藍藍鯨鯨鯨
在n特別大的時候,n和n^2比大小啊可以忽略,o()看的是最大的那一級
9樓:赧衣牟若彤
時間複雜度
演算法分析
同一問題可用不同演算法解決,而一個演算法的質量優劣將影響到演算法乃至程式的效率。演算法分析的目的在於選擇合適演算法和改進演算法。一個演算法的評價主要從時間複雜度和空間複雜度來考慮。
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))
我們一般所討論的是除正常佔用記憶體開銷外的輔助儲存單元規模。
為啥氣泡排序的最優時間複雜度是o(n)不是o(1)啊?
10樓:匿名使用者
就是o(n),維基百科是對的~
初始時陣列中的數就已經排列完成了的話,還需要掃一遍陣列的,所以是o(n)~
不懂可問,滿意望採納謝謝!
快速排序方法的時間複雜度為o(n^2)=n(n-1)/2中o()是什麼意思? 200
11樓:匿名使用者
o(1): 表示演算法
的執行時間為常量
o(n): 表示該演算法是線性演算法
o(log2n): 二分查詢演算法
o(n2): 對陣列進行排序的各種簡單演算法,例如直接插入排序的演算法。
o(n3): 做兩個n階矩陣的乘法運算
o(2n): 求具有n個元素集合的所有子集的演算法o(n!):
求具有n個元素的全排列的演算法o(n2)表示當n很大的時候,複雜度約等於**2,c是某個常數,簡單說就是當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))
為演算法的漸進時間複雜度,簡稱時間複雜度。
12樓:匿名使用者
1)對於你的問題簡單解釋如下:
理論計算機研究中,衡量演算法一般從兩個方面分析:時間複雜度和空間複雜度。空間複雜度跟時間複雜度是類似的,下面簡單解釋一下時間複雜度:
對於一個資料規模為n的問題,解決該問題的演算法所用時間可以用含有n的函式t(n)來表示。對於絕大多數情況,我們只需要瞭解演算法的一般效能而不考慮細節,也就是說,我們只關心函式t(n)的表示式的形式,而不關心表示式的常數係數等與資料規模沒有關係的量值。對於函式t(n),我們又進一步將它簡化為o(n),即只考慮演算法平均執行時間的「瓶頸」,也就是t(n)表示式中,關於變數n增長最快的哪一項。
比如下面的**:
for(int i=1; i<=n*2; i++)for(int j=1; j<=n; j++)// do something here
那麼這個演算法的時間複雜度就是o(n^2),因為它有兩層迴圈,每層迴圈的資料規模都是n。注意第一層迴圈(外迴圈)要迭代n*2次,則實際上t(n)=2*n*n,而對於o(n)來說,我們忽略了常數2,只保留了n^2。這就是大o記法的一個概括,並不精確。
對於時間複雜度的更精確、深入的解釋,可以自己查閱《演算法導論》第一章。
2)更正你的問題:快速排序演算法的時間複雜度應該為o(n lg n)。注意三種時間複雜度符號表示的不同意義!
英文字母o代表的是平均執行時間,因此對於快速排序來說應該是o(n lg n)。而使用下界函式omega或者上界函式theta則分別表示演算法執行的最快和最慢時間。對於未使用隨機化的快速排序,理論上可以證明,存在某一方法構造出一組資料使快速排序「退化」成平方複雜度演算法即theta(n^2)。
但是對於其o(n)表示法應該為o(n^2)。
時間複雜度是o(n^2)是什麼意思?
13樓:白衣太史
這個意思是說一個演算法時間的消耗是和其計算步數成平方增長的。
n^2就是n的平方,在一般的輸入框裡面沒法打出上標,才這麼寫的。
如果某演算法,算十步的時間是100秒,而其時間複雜度是o(n^2)的話,那麼算11步的時間大概就是121秒
我的解釋比較粗俗,這個裡面的回答很專業,但是如果沒有相應基礎,不是很好懂,看看你能看懂不?
怎樣才能學好資料結構，還有程式設計，作為計算機專業的學生，我很沒有目標
好好學習 軟體之家畢業設計網 做計算機畢業設計 那主要bai是看你畢業是du否想找對口專業的工作zhi，如果想找的話dao，那你就回待好好學了答，最主要的目的是對付考試，怎麼學無非就是多學多實踐，學什麼鑽什麼！我有個同學也是學計算機的，學的是程式設計，他把學過的 都自己在從新寫個幾十遍。至於迷茫大可...
在資料結構中,資料的邏輯結構,資料的儲存結構及資料的運算之間存在著怎麼樣的關係
資料的邏輯結構決定了資料間運算關係的具體定義，而資料的儲存結構與資料的運算方法，沒有直接的關係，資料的儲存結構決定了維護資料邏輯結構時各種操作的運算複雜程度。在資料結構中,資料的邏輯結構,資料的儲存結構及資料的運算之間存在著怎麼樣的 資料的儲存結構及資料的運算之間存在著怎樣的關係 在資料結構中，邏輯...
計算機結構及工作原理，簡述計算機的組成及工作原理
計算機的組成結構包括硬體系統 軟體系統。其工作原理是按照記憶體中發出的指令進行資料運算和邏輯加工，從而完成規定操作。具體如下 計算機的硬體包括電源 主機板 cpu 顯示器 記憶體 硬碟 音效卡等，計算機的軟體包括作業系統 系統軟體 語言處理系統 資料庫管理系統 服務程式等等。計算機的基本工作原理 計...