iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 6
1
自我挑戰組

計算機概論X30天系列 第 6

Day6:[演算法]演算法是什麼?讓數學王子高斯教你什麼是演算法

▌挑戰簡介

  • 題目:計算機概論X30天

  • 挑戰內容:連續30天紀錄計算機概論、離散數學、演算法、資料結構等課程,還有自己學習程式的心得體悟。

▌演算法(algorithm)的威力

前天說過如何利用算時間複雜度(Time Complexity)來檢測程式的效率,那今天就來介紹演算法(algorithm),但如果只是直接講解演算法定義,那肯定是很無聊,也不好懂。

尼采說「人們無法理解未曾經歷的事情」,還是直接看例子感受一下演算法的有趣吧!

1+2+3...+100怎麼算

要如何把1加到100呢?太簡單了,就用for迴圈囉!

function add() {
    var sum = 0;
    for (var i = 0; i <= 100; i++) {
        sum = sum + i  //0+1+2.....100停下來
    }
    console.log(sum)
}

go() //輸出5050

1+2+3...+n怎麼算

小看我的智商嗎?把100改成n放進去囉

function add(n) {
    var sum = 0;
    for (var i = 0; i <= n; i++) {
        sum = sum + i  //0+1+2.....n停下來
    }
    console.log(sum)
}

go(100) //輸出5050
go(200) //輸出20100

沒錯,這是解決問題的方法。

有更好的方法嗎?

高斯的演算法

數學小王子高斯說:「我有!」

聰明的數學家高斯,在小學的時候就想到了如何破解無聊老師給的「1加到100」這種莫名其妙的問題

當他的同學還在用1+2+3+...100慢慢算時,他直接用(1+100)X100%2解決了這個問題
也就是首項加末項乘以項數除以2

// 天才高斯的演算法,(1+100)*100/2

function gogo(n) {
    sum = (1 + n) * n / 2  
    console.log(sum)
}

gogo(100) //5050

所以呢?

哦....是喔...所以呢?

高斯的寫法是好在哪裡?

啊不就是比較短而已啊?

有什麼不一樣?

有!如果看過我的上一篇,就知道他們的時間複雜度(Time Complexity)不ㄧ樣

時間複雜度(Time Complexity)分析

第一個寫法

function add(n) {
    var sum = 0;
    for (var i = 0; i <= n; i++) {
        sum = sum + i  //要跑n個迴圈,例如n=1000就要跑1000個迴圈
    }

}

第一個寫法因為使用了迴圈,當有n個數字時,就要跑n個迴圈,因此時間複雜度是O(n)

高斯寫法

function gogo(n) {
    sum = (1 + n) * n / 2  //不管n多大,例如n=1000000,這行也只用跑一次  
    console.log(sum) 
}

高斯的寫法不需要用到迴圈,不管n多大,也只需要一行,因此時間複雜度是O(1)

一個時間複雜度是O(n),一個時間複雜度是O(1)

當n不大的時候兩者的執行效率不會差很多,但是當n愈來愈大時,高斯的演算法就會明顯地比他的同學還要好。

https://ithelp.ithome.com.tw/upload/images/20181020/20112011LzUSOSLEC0.png

上圖呈現了當數據不同時,複雜度的差異

複習:時間複雜度不等同於「花費的時間」,而是指「隨著數據規模增大所增加的時間資源消耗變化」,因此又稱為漸進時間複雜度。

總結:什麼是演算法?

所以究竟什麼是算法(Algorithm)?
——說白了就是一套解決問題的方法(只不過把電腦的方法稱為「算法」感覺比較厲害)

那基於不同問題,計算機科學家就發明不同的方法

像是

  • 處理數據排序問題:有氣泡排序(bubble sort)、插入排序(insertion sort)...等
  • 處理資料搜索問題:有深度優先算法(DFS)、廣度優先算法(BFS)...等

不只是計算機,人做事也有方法,比如說「想閱讀書本第N章節的內容」,那「從目錄檢索」這個行為,可能就會比「從頭開始翻閱」來的有效率,更是一種好方法。

其實做事情的方法有很多,許多方法都能解決問題;只是一個「好方法」,更能比其他方法有效率解決問題。

就像高斯跟他同學的寫法,其實也都能解決問題。只是,在N很大的情況,高斯的演算法更明顯的有效率。

總而言之

如果說「方法」是人類解決問題的步驟,那「算法」就是電腦處理數據的步驟
如果說「數據結構」是電腦儲存數據的的結構,「算法」就是電腦操作數據的一組方法。

算法這個詞聽起來很厲害,但其實不過就是一些處理問題的好步驟而已

參考資料與推薦閱讀

  • 程杰,2011,《大話數據結構》:高斯的點子是從這裡來的
    這本書很有趣,整本以一個計算機教師為主角用對話的方式講解。
  • 王爭・極客時間APP・《數據結構與算法之美》

上一篇
Day5:[演算法]如何衡量程式的效率?——論時間複雜度(Time Complexity)
下一篇
Day7: [演算法] 用JS實現冒泡排序
系列文
計算機概論X30天30

尚未有邦友留言

立即登入留言