1樓:林柯伊南
時間復抄雜度不是相對於襲
程式而言的,而是指問題的複雜
例如排序,對分查詢在最劣情況下也是平方問題,但對於絕大多數問題而言,我們只關心平均效率。
例如稀疏陣列,可以降低對空間的要求,但當有用資料超過一定規模,執行速度將急劇下降。
次數超過4的多項式沒有平凡解,所以被成為大o的n次方問題,這樣的問題總是需要那麼多時間才能完成計算,這就是時間的複雜度。
任何資料的壓縮都有極限,越是隨機的資料,越不能找到良好的資料結構,這就是空間的複雜性。
實際上如果沒有好的演算法和資料結構,大多數程式是無法真正做到應用的。
2樓:
時間複雜度是就演算法而言的,與語言無關,時間複雜度不需要計算,是通過理論分析出來的,有很多方法來分析時間複雜度。
c語言演算法的時間複雜度如何計算啊?
3樓:熊貓
看看這個 每個迴圈都和上一層迴圈的引數有關。 所以要用地推公式: 設i(n)表示第一層迴圈的i為n時的迴圈次數,注意到他的下一層迴圈次數剛好就是n,分別是0,1,2...
n-1 所以,把每一層迴圈設一個函式分別為:j(n),k(n),t(n) 則有 i(n)=j(0)+...+j(n-1) j(n)=k(0)+...
+k(n-1) k(n)=t(0)+...+t(n-1) i(0)=j(0)=k(0)=0 t(n)=1 而總迴圈數是i(0)+i(1)...+i(n-1) 可以根據遞推條件得出準確值 所以演算法複雜度是o(i(0)+i(1)...
+i(n-1))
記得采納啊
4樓:匿名使用者
求解演算法的時間複雜度的具體步驟是:
(1)找出演算法中的基本語句;
演算法中執行次數最多的那條語句就是基本語句,通常是最內層迴圈的迴圈體。
(2)計算基本語句的執行次數的數量級;
只需計算基本語句執行次數的數量級,這就意味著只要保證基本語句執行次數的函式中的最高次冪正確即可,可以忽略所有低次冪和最高次冪的係數。這樣能夠簡化演算法分析,並且使注意力集中在最重要的一點上:增長率。
(3)用大ο記號表示演算法的時間效能。
將基本語句執行次數的數量級放入大ο記號中。
如果演算法中包含巢狀的迴圈,則基本語句通常是最內層的迴圈體,如果演算法中包含並列的迴圈,則將並列迴圈的時間複雜度相加。例如:
for(i=1;i<=n;i++) x++; for(i=1;i<=n;i++)
for(j=1;j<=n;j++) x++; 第一個for迴圈的時間複雜度為ο(n),第二個for迴圈的時間複雜度為ο(n2),則整個演算法的時間複雜度為ο(n+n2)=ο(n2)。
常見的演算法時間複雜度由小到大依次為:
ο(1)<ο(log2n)<ο(n)<ο(nlog2n)<ο(n2)<ο(n3)<...<ο(2n)<ο(n!)ο(1)表示基本語句的執行次數是一個常數,一般來說,只要演算法中不存在迴圈語句,其時間複雜度就是ο(1)。ο(log2n)、ο(n)、ο(nlog2n)、ο(n2)和ο(n3)稱為多項式時間,而ο(2n)和ο(n!
)稱為指數時間。電腦科學家普遍認為前者是有效演算法,把這類問題稱為p類問題,而把後者稱為np問題。
這隻能基本的計算時間複雜度,具體的執行還會與硬體有關。
5樓:血刺廢車
(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(log(2)n),線性階o(n), 線性對數階o(nlog(2)n),平方階o(n^2),立方階o(n^3),..., k次方階o(n^k),指數階o(2^n)。隨著問題規模n的不斷增大,上述時間複雜度不斷增大,演算法的執行效率越低。
6樓:問豐建思蓮
在計算之前取得系統的滴答數
inttbegin
=gettickcount();
計算完成過後再次呼叫減去滴答數就行了,單位msinttend
=gettickcount()
-tbegin;
還有其他更精確的函式,搞忘了,你最好查下msdn純c下不要用c自帶的計算滴答數的函式,不精確,應該使用系統的
c語言中的演算法裡,時間複雜度可以記為o(n平方)。字母o 表示什麼?
7樓:匿名使用者
計算機科來學中,算自法的時間複雜度是一個函式,它定量描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述,不包括這個函式的低階項和首項係數。
代表「order of ...」(......階)的大 o,最初是一個大寫的希臘字母希臘字母'ο'(omicron),現今用的是大寫拉丁字母『o』。
8樓:本澤馬
大baio符號是用於描述函式漸du近行為的數zhi學符號,一般用來刻畫dao
被截斷的無窮級數剩餘版項權,最先由德國數論學家保羅·**曼在其著作《解析數論》引入,並在另外一個德國數論學家艾德蒙·朗道的著作中推廣,所以又稱為朗道符號。大o是"order of..." (......階)的意思,最初是一個大寫的希臘字母'o'(omicron),現在用的大寫的英文字母'o'。
資料結構,c語言,分析一下這個函式的功能和時間複雜度 20
9樓:宥噲
c語言是bai一種程式設計的語du言,程式設計的語言有很多種。而資料zhi結dao構則是講的是關於一些回資料的理論知識。可以說答不管什麼程式語言都能用到資料結構的知識,資料結構是程式設計基礎又核心的知識。
可以將c語言想象為一種語言,那麼資料結構就是一種說話的技巧,如何讓你說話更簡潔,有邏輯,容易讓人聽懂,這表達技巧不管你用中文或者english都可以用上。當然,如果你想成為一個優秀的程式設計人員,資料結構是必須掌握好的
什麼是時間複雜度空間複雜度
1 時間複雜度是指執行演算法所需要的計算工作量。時間複雜度是一個函式，它定性描述了該演算法的執行時間。這是一個關於代表演算法輸入值的字串的長度的函式。時間複雜度常用大o符號表述，不包括這個函式的低階項和首項係數。2 空間複雜度是指執行這個演算法所需要的記憶體空間。空間複雜度需要考慮在執行過程中為區域...
時間複雜度的定義，C 中時間複雜度是什麼意思
1 時間複雜度 1 時間頻度 一個演算法執行所耗費的時間，從理論上是不能算出來的，必須上機執行測試才能知道。但我們不可能也沒有必要對每個演算法都上機測試，只需知道哪個演算法花費的時間多，哪個演算法花費的時間少就可以了。並且一個演算法花費的時間與演算法中語句的執行次數成正比例，哪個演算法中語句執行次數...
c語言，程式設計演算法最壞情況下的時間複雜度可以與平均情況的時
最差情況下的復 雜度是所有可能的輸入資料所消耗的最大資源，如果最差情況下的複雜度符合我們的要求，我們就可以保證所有的情況下都不會有問題。某些演算法經常遇到最差情況。比如一個查詢演算法，經常需要查詢一個不存在的值。也許你覺得平均情況下的複雜度更吸引你，可是平均情況也有幾點問題。第一，難計算，多數演算法...