算法設(shè)計的要求:正確性,可讀性,健壯性和效率與低存儲量需求.
為了比較同一問題的不同算法,通常的做法是從算法中選取一種對于所研究的問題來說是基本操作的原操作,以該操作的重復(fù)執(zhí)行次數(shù)作為算法的時間量度.
例如:
for(i=1;i<=n;i++){
? ? for(j=1;j<=n;j++){
? ? ? ? sum=i*j;
}}
在代碼中,乘法是該循環(huán)的基本操作,整個算法的執(zhí)行與該基本操作重復(fù)的次數(shù)成正比,記作
.
1.時間復(fù)雜度:
他表示隨規(guī)模n的增大,算法執(zhí)行時間的增長率和的增長率相同,稱為算法的漸進時間復(fù)雜度,簡稱時間復(fù)雜度.
如何使用時間復(fù)雜度描述?
首先我們需要確定一個基本操作n,根據(jù)這個基本操作的重復(fù)次數(shù)來表示O(f(n)).
例如常量階O(1),線性階O(n),平方階O(),對數(shù)階O(
),指數(shù)階O(
)等等.
看樣子回頭又得補高數(shù)了...
補充:由于算法的時間復(fù)雜度考慮的只是對于問題規(guī)模n的增長率,則在難以精確計算基本操作執(zhí)行次數(shù)的情況下,只需求出它關(guān)于n的增長率或階即可.
補充:for(i=1;i<=n;i++){a++};
for(i=1;i<=n;i++){for(j=1;j<=n;j++){a++;}
第一個for循環(huán)時間復(fù)雜度是O(n),第二個是O(n^2),那么整個就是O(n+n^2).
一般來說，只要算法中不存在循環(huán)語句，時間復(fù)雜度就為O(1)。
2.空間復(fù)雜度
通常來說，只要算法不涉及到動態(tài)分配的空間，以及遞歸、棧所需的空間，空間復(fù)雜度通常為O(1)；
一般的遞歸算法空間復(fù)雜度為O(n^2),
