學習算法應該首先了解怎么去評估一個算法的好壞以及怎么去計算一個算法的效率凶朗,只有知道了這個,才能夠寫出好的算法
1、下面了解一些基本概念:
- 函數(shù)漸近增長:給定兩個函數(shù)f(n)和g(n),如果存在一個整數(shù)N臭脓,使得對于所有的n>N,f(n)總是比g(n)大腹忽,那么可以說f(n)的漸近快于g(n)
- 算法的時間復雜度:在進行算法分析的時候来累,總的執(zhí)行次數(shù)T(n)是關于問題規(guī)模n的一個函數(shù),分析T(n)隨n的變化情況來確定T(n)的數(shù)量級窘奏。算法的時間復雜度嘹锁,也就是算法的時間量度,記作:T(n)= O(f(n))着裹,表示隨著問題規(guī)模n的擴大兼耀,算法執(zhí)行的時間增長率和f(n)的增長率相同,稱為算法的漸近時間復雜度求冷,簡稱時間復雜度瘤运,其中f(n)表示關于問題規(guī)模n的某個函數(shù)。
- O():規(guī)定使用O()來表示算法的時間復雜度匠题,稱之為大O記法
2拯坟、了解了基本基本概念之后,就來學習下怎么進行大O的推導吧
推導大O分為三個部分
1. 使用常數(shù)1取代f(n)中所有加法常數(shù)
2. 只保留最高項階
3. 如果最高項階存在同時系數(shù)不是1韭山,那么去掉這個系數(shù)