算法是解決特定問題求解步驟的描述，在計算機(jī)中表現(xiàn)為指令的有限序列篷帅，并且指令表示一個或多個操作。
一個簡單的加法算法

int i竿滨，sum=0权埠，n=100;
sum = (1+n)*n/2;
printf("%d",sum);

• 算法定義

算法是解決特定問題求解步驟的描述担孔，在計算機(jī)中表現(xiàn)為指令的有限序列椭蹄，并且每條指令表示一個或多個操作檬贰。

• 算法的特性

  • 輸入輸出
    • 算法具有零個或多個輸入惭嚣。
    • 算法至少有一個或多個輸出遵湖。
  • 有窮性
    指算法在執(zhí)行有限的步驟之后，自動結(jié)束而不會出現(xiàn)無限循環(huán)晚吞，并且每一步驟在可接受的時間內(nèi)完成
  • 確定性
    算法的每一步驟都具有確定的含義延旧，不會出現(xiàn)二義性。
  • 可行性
    算法的每一步都必須是可行的槽地，也就是說迁沫，每一步都能通過執(zhí)行有限次數(shù)完成。

• 算法設(shè)計的要求

  • 正確性
    算法的正確性是指算法至少應(yīng)該具有輸入捌蚊，輸出和加工處理無歧義性集畅，能正確反應(yīng)問題的需求，能夠得到問題的正確答案缅糟。
    1.算法程序沒有語法錯誤
    2.算法程序?qū)τ诤戏ǖ妮斎霐?shù)據(jù)能夠產(chǎn)生滿足要求的輸出結(jié)果挺智。
    3.算法程序?qū)τ诜欠ǖ妮斎霐?shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果。
    4.算法程序?qū)τ诰倪x擇的窗宦，甚至刁難的測試數(shù)據(jù)都有滿足要求的測試結(jié)果赦颇。
    一般租到層次3就行。
  • 可讀性
    算法設(shè)計的另一目的是為了便于閱讀赴涵，理解和交流媒怯。
  • 健壯性
    當(dāng)輸入數(shù)據(jù)不合法時，算法也能做出相關(guān)處理髓窜，而不是產(chǎn)生異成劝或莫名其妙的結(jié)果。
  • 時間效率高和存儲量低

• 算法效率的度量方法寄纵。

  • 事后統(tǒng)計方法
    這種方法主要是通過設(shè)計好的測試程序和數(shù)據(jù)鳖敷，利用計算機(jī)計時器對不同算法編制的程序的運行時間進(jìn)行比較，從而確定算法效率的高低程拭。
    • 實際上因為哄陶，編寫測試程序復(fù)雜，硬件不同導(dǎo)致時間不同哺壶，測試數(shù)據(jù)的差異大屋吨，設(shè)計困難蜒谤，一般不考慮用這個方法。
  • 事前分析估算方法
    在計算機(jī)程序編制前至扰，依據(jù)統(tǒng)計方法對算法進(jìn)行估算鳍徽。有以下因素
    • 算法采用的策略、方法敢课。
    • 編譯產(chǎn)生的代碼質(zhì)量阶祭。
    • 問題的輸入規(guī)模。
    • 機(jī)器執(zhí)行指令的速度直秆。
  • 拋開計算機(jī)硬件濒募，軟件有關(guān)的因素，一個程序的運行時間圾结，依賴于算法的好壞和問題的輸入規(guī)模瑰剃。

• 函數(shù)的漸近增長

給定兩個函數(shù)f(n)和g(n)，如果存在一個整數(shù)N筝野，使得對于所有n>N,f(n)總是比g(n)大晌姚，那么，我們說f(n)的增長漸近快于g(n)歇竟。
實際上就是最高項越大越復(fù)雜 n^3>n2挥唠。

• 算法時間復(fù)雜度

  • 算法時間復(fù)雜度定義
    在進(jìn)行算法分析是，語句總的執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)焕议，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級宝磨。算法的時間復(fù)雜度，也就是算法的時間度量盅安，記作:T(n) =O(F(n)).它表示隨問題規(guī)模n的增大唤锉，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱作算法的漸近時間復(fù)雜度宽堆，簡稱為時間復(fù)雜度腌紧。其中f(n)是問題規(guī)模n的某個函數(shù)茸习。
    O(1)叫常數(shù)階畜隶、O(n) 叫線性階、O（n^2)叫做平方階号胚，當(dāng)然籽慢，還有其他的一些階，我們之后會介紹
  • 推導(dǎo)大O階方法
    1.用常數(shù)1取代運行時間中所有加法常數(shù)
    2.在修改后的運行次數(shù)函數(shù)中猫胁，只保留最高階項箱亿。
    3 .如果最高階項存在且不是1，則去除與這個項相乘的常數(shù)弃秆。
    得到的結(jié)果就是大O階届惋。
  • 常數(shù)階
    只要執(zhí)行的單個單元髓帽，最高項也是常數(shù)，則都寫成O(1)
  • 線性階
    就是循環(huán)一次的差不多脑豹，O(n)郑藏；
  • 對數(shù)階

      while(count<n){
      count = count * 2; 
      }```
    

  每次乘以2之后都更接近n
  2^n=n;
  所以是log（2） n底數(shù)是2.
  這個循環(huán)的復(fù)雜度也是O(log（2） n).
  • 平方階
    O(n^2)

• 常見的時間復(fù)雜度

O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)<O(2^n)<O(n!)<O(nn)

• 最壞情況與平均情況

  • 最壞情況運行時間是一種保證，那就是運行時間將不會再壞了瘩欺，再應(yīng)用中必盖，這是一種最重要的需求，通常俱饿，除非特別指定歌粥，我們提到的運行時間都是最壞情況的運行時間。
  • 平均運行時間是所有情況中最有意義的拍埠，因為它是期望的運行時間失驶。

• 算法空間復(fù)雜度

算法空間復(fù)雜度通過計算算法所需的存儲空間實現(xiàn)，算法空間復(fù)雜度的計算公式記作：S(n) = O(f(n)).其中械拍，n為問題的規(guī)模突勇，f(n)為語句關(guān)于n所站存儲空進(jìn)的函數(shù)。