算法的定義及特性:

(1)有窮性:一個(gè)算法必須總是執(zhí)行有窮步后結(jié)束,且每一步都必須在有窮時(shí)間內(nèi)完成.

(2)確定性.

(3)可行性.

(4)輸入:可以有0個(gè)或多個(gè)輸入.

(5)輸出:一個(gè)或多個(gè)輸出.

評(píng)價(jià)算法優(yōu)劣的基本標(biāo)準(zhǔn):

(1)正確性

(2)可讀性

(3)健壯性

(4)高效性

算法的時(shí)間復(fù)雜度:

1.算法的執(zhí)行時(shí)間和語(yǔ)句的頻度

一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有的語(yǔ)句執(zhí)行時(shí)間的總和,而語(yǔ)句的執(zhí)行時(shí)間則為該語(yǔ)句的重復(fù)執(zhí)行的次數(shù)和執(zhí)行一次所需時(shí)間的乘積.

2.問(wèn)題規(guī)模和算法的時(shí)間復(fù)雜度

算法求解問(wèn)題的輸入量成為問(wèn)題的規(guī)模,一般用n表示.

一個(gè)算法的時(shí)間復(fù)雜度是該算法的執(zhí)行時(shí)間,記作T(n),T(n)是該算法所求解問(wèn)題規(guī)模n的函數(shù).當(dāng)問(wèn)題的規(guī)模n趨向無(wú)窮大時(shí),T(n)的數(shù)量級(jí)稱為算法的漸進(jìn)時(shí)間復(fù)雜度,記作:

T(n) = O(f(n))

算法的空間復(fù)雜度:

算法的存儲(chǔ)需求.它也是問(wèn)題規(guī)模n的函數(shù),記作:

S(n) = O(f(n))