tóng yī wèn tí kě yòng bù tóng suàn fǎ jiě jué， ér yī gè suàn fǎ de zhì liàng yōu liè jiāng yǐng xiǎng dào suàn fǎ nǎi zhì chéng xù de xiàolǜ。 suàn fǎ fēn xī de mùdì zài yú xuǎn zé hé shì suàn fǎ hé gǎi jìn suàn fǎ。 yī gè suàn fǎ de píng jià zhù yào cóng shí jiān fù zá dù hé kōng jiān fù zá dù lái kǎo lǜ。
1、 shí jiān fù zá dù
（ 1） shí jiān pín dù
yī gè suàn fǎ zhí xíng suǒ hào fèi de shí jiān， cóng lǐ lùn shàng shì bù néng suàn chū lái de， bì xū shàng jī yùn xíng cè shì cái néng zhī dào。 dàn wǒ men bù kě néng yě méi yòu bì yào duì měi gè suàn fǎ dū shàng jī cè shì， zhǐ xū zhī dào nǎ gè suàn fǎ huā fèi de shí jiān duō， nǎ gè suàn fǎ huā fèi de shí jiān shǎo jiù kě yǐ liǎo。 bìng qiě yī gè suàn fǎ huā fèi de shí jiān yǔ suàn fǎ zhōng yǔ jù de zhí xíng cì shù chéng zhèng bǐ lì， nǎ gè suàn fǎ zhōng yǔ jù zhí xíng cì shù duō， tā huā fèi shí jiān jiù duō。 yī gè suàn fǎ zhōng de yǔ jù zhí xíng cì shù chēng wéi yǔ jù pín dù huò shí jiān pín dù。 jì wéi t(n)。
（ 2） shí jiān fù zá dù
zài gāng cái tí dào de shí jiān pín dù zhōng， n chēng wéi wèn tí de guī mó， dāng n bù duàn biàn huà shí， shí jiān pín dù t(n) yě huì bù duàn biàn huà。 dàn yòu shí wǒ men xiǎng zhī dào tā biàn huà shí chéng xiàn shénme guī lǜ。 wèicǐ， wǒ men yǐn rù shí jiān fù zá dù gài niàn。
yī bān qíng kuàng xià， suàn fǎ zhōng jī běn cāo zuò chóngfù zhí xíng de cì shù shì wèn tí guī mó n de mǒu gè hán shù， yòng t(n) biǎo shì， ruò yòu mǒu gè fǔ zhù hán shù f(n), shǐ dé dāng n qū jìn yú wú qióng dà shí， t（ n)/f(n) de jí xiàn zhí wéi bù děng yú líng de cháng shù， zé chēng f(n) shì t(n) de tóng shù liàng jí hán shù。 jì zuò t(n)=o(f(n)), chēng o(f(n)) wéi suàn fǎ de jiàn jìn shí jiān fù zá dù， jiǎn chēng shí jiān fù zá dù。
zài gè zhǒng bù tóng suàn fǎ zhōng， ruò suàn fǎ zhōng yǔ jù zhí xíng cì shù wéi yī gè cháng shù， zé shí jiān fù zá dù wéi o(1), lìng wài， zài shí jiān pín dù bù xiāng tóng shí， shí jiān fù zá dù yòu kě néng xiāng tóng， rú t(n)=n2+3n+4 yǔ t(n)=4n2+2n+1 tā men de pín dù bù tóng， dàn shí jiān fù zá dù xiāng tóng， dū wéi o(n2)。
àn shù liàng jí dì zēng pái liè， cháng jiàn de shí jiān fù zá dù yòu：
cháng shù jiē o(1), duì shù jiē o(log2n), xiàn xìng jiē o(n),
xiàn xìng duì shù jiē o(nlog2n), píng fāng jiē o(n2)， lì fāng jiē o(n3),...，
k cì fāng jiē o(nk), zhǐ shù jiē o(2n)。 suí zhe wèn tí guī mó n de bù duàn zēng dà， shàng shù shí jiān fù zá dù bù duàn zēng dà， suàn fǎ de zhí xíng xiàolǜ yuè dī。
2、 kōng jiān fù zá dù
yǔ shí jiān fù zá dù lèi sì， kōng jiān fù zá dù shì zhǐ suàn fǎ zài jì suàn jī nèi zhí xíng shí suǒ xū cún chǔ kōng jiān de dù liàng。 jì zuò :
s(n)=o(f(n))
wǒ men yī bān suǒ tǎo lùn de shì chú zhèng cháng zhàn yòng nèi cún kāi xiāo wài de fǔ zhù cún chǔ dān yuán guī mó。 tǎo lùn fāng fǎ yǔ shí jiān fù zá dù lèi sì， bù zài zhuì shù。 |
|
|