算法定義

• 確定性
• 能行性
• 輸入
• 輸出
• 有窮性
  計算過程：滿足前四條不滿足有窮性
  OS就是計算過程

算法好壞的衡量尺度

• 問題的規模 ：輸入數據量的測度
• 基本運算：兩個實矩陣的乘法：實數的乘法（及加法）；數表的排序：表中的兩個數據項進行比較
• 算法的計算量函數

算法的計算量函數

時間復雜性
問題規模的某個函數來表示算法的基本運算量,這個表示基本運算量的函數

表示漸近時間復雜性的三個記號

T(n)=O(f(n))
T(n)=Ω(f(n))
T(n)=Θ(f(n)

• T(n)= O(f(n))：

若存在c > 0，和正整數n0≥1，使得當n≥n0時，總有T(n)≤cf(n)
給出了算法時間復雜度的上界，復雜度不可能比cf(n)更大

• T(n)=Ω(f(n))

若存在c > 0，和正整數n0≥1，使得當n≥n0時，存在無窮多個n ，使得T(n)≥cf(n)成立
給出了算法時間復雜度的下界，復雜度不可能比cf(n)更小

• T(n)=Θ(f(n))

若存在c1,c2>0，和正整數n0≥1，使得當n≥n0時，總有 T(n)≤c1f(n)，且有無窮多個n，使得T(n)≥c2f(n)成立,即：T(n)= O(f(n))與T(n)=Ω(f(n))都成立
既給出了算法時間復雜度的上界，也給出了下界

評價算法的主要方面

正確性：首要因素
健壯性：對正確、不正確的輸入的應對處理
簡答性：可讀性好，易調試、改進
高效性： 時間、空間復雜度較小

最優性：證明所給算法是解決同一類問題中最好的

算法的應用——實例

• Google PageRank

評估網頁重要性

• Google Map, Baidu Map

路徑規劃

• 金融領域

算法交易，風險控制

總結

以上是生活随笔為你收集整理的1算法基本概念的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。