2021計算機考研備考：時間復雜度計算

　　對于打算報考2021考研計算機的考生們來說復習是難點，很多本專業(yè)或者跨專業(yè)的學生在備考的時候覺得時間復雜度的計算不好掌握，經(jīng)常題干中代碼一變就不知道該怎么計算，下面小編整理了詳細內(nèi)容，供大家參考。

　　算法的時間量度指的是算法中基本操作重復執(zhí)行的次數(shù)。

　　一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n)，算法的時間量度記作T(n)=O(f(n))，通常稱為時間復雜度，其中O的形式定義為：若f(n)是正整數(shù)n的一個函數(shù)，則xn=O(f(n))表示存在一個正的常數(shù)M，使得當n&gen0時都滿足|xn|&leM|f(n)|。

　　注意：基本操作是其重復執(zhí)行的次數(shù)和算法的執(zhí)行時間成正比的原操作，多數(shù)情況下它是最深層循環(huán)內(nèi)的語句中的原操作，它的執(zhí)行次數(shù)和包含它的語句的頻度是相同的。語句的頻度指的是該語句重復執(zhí)行的次數(shù)。

　　計算時間復雜度關(guān)鍵的基本操作。例如，在下列3個程序段中：

　　(1)++x s=0

　　(2)for (i =1 i <=n ++i) ++x s+=x

　　(3)for (j =1 j<=n ++j)

　　for (k =1 k<=n ++k) ++x s+=x

　　含基本操作“x增1”的語句的頻度分別為1、n和n2，則這3個程序段的時間復雜度分別為O(1)、O(n)和O(n2)。算法還可能呈現(xiàn)的時間復雜度有對數(shù)階O(log2n)、指數(shù)階O(2n)等。

　　備考過程中，你可能很努力卻還收效甚微，但我們要記住，量變堅持下去才會形成質(zhì)變。星光不問趕路人，時光不負有心人。你的堅持，終將美好。

　　(注：本文來自網(wǎng)絡，如有侵權(quán)，請聯(lián)系刪除)