<<回科普文章主選單>>

Linear & Non Linear

線性 & 非線性


線性跟非線性的比較是在深度學習裡面常常會碰到的問題。從分割,分類,到對位都會碰到線性跟非線性的比較。在這一篇文章裡,我們要探索的是最基本的線性和非線性比較,線性數據結構跟非線性數據結構的區別。

線性數據結構包含的就是連續性的數據,任一個數據跟前面和後面的數據都有關聯。這個觀念就好比一整套叢書,例如海賊王一到一百集。如果你要把這一套叢書放到書架上,你會怎麼擺放呢?你大概會從書架上空出一個大空間,把書一本一本照順序放,第一集放到第二集之前,第九十七集放到第九十六集之後。這樣擺放的方式有什麼特點呢?第一,因為所有的書都放在一起,照順序放,要從第一集看到最後一集很簡單,就從第一集開始,一直往右移動,一直線的走下去就可以了。第二,線性數據很好建構,因為只要空出足夠的空間,擺出第一本書,再決定總共有幾本書,後面的擺放就非常的輕鬆容易,一本接著一本放了。第三,因為是這種一本接著一本的擺放方式,對空間的使用非常不友善,一定要強制性的空出足夠的空間。以海賊王的叢書來講,若空出來的空間只能放九十本書,就無法用來儲存海賊王的叢書。第四,因為線性數據是從第一個數據開始找,時間複雜度O跟數據量的大小成正相關,數據量越多,跑得越慢,數據量越少,會跑得越快。以電腦數據來講,線性數據結構有陣列,串列,佇列,棧。

非線性數據結構相比起來就是放非連續性的數據,要分多層次來放置數據。舉例來說,現在你去圖書館找書的方式就比較像是非線性數據。因為你不是先找第一本書在哪裏,然後按順序找書。因為書是分很多不同櫃子排列的,在不同層樓中。在不同櫃子裡,不同的類型的書又放不同的地

圖一

方。這種放書方式有什麼特點?第一,它比較複雜。可以簡單的想像要成功的把一個圖書館的書有條理的分層擺放是一個複雜的工程。第二,因為複雜,所以也較不容易理解。比起要從擺在一堆的海賊王叢書裡找出第幾本海賊王來說,要了解圖書館裡的擺書方式是不容易的。第三,要在圖書館找書是要分步驟的。要先找到是在第幾層,接著找到是在那一層的哪一個櫃子,在櫃子裡的哪一個區塊,然後才能找到書。第四,這種放書的方式,不需要把一百本書一起放到書架上,跟海賊王叢書一樣需要空出連續一百本的空間,而是可以東塞一本,西塞一本,不需要特別騰出空間就可以塞完全部的書了。第五,跟線性數據不一樣,時間複雜度O並不會隨數據量的增長而上升,因為不管一個圖書館是有一千本還是一萬本書,找每一本書的步驟都是一樣的,找層,找櫃,找區塊,然後找書,固定的步驟,固定的複雜度。以電腦數據來講,非線性數據結構有圖和樹。


參考文獻:

https://www.tutorialspoint.com/difference-between-linear-and-non-linear-data-structures#:~:text=In%20linear%20data%20structure%2C%20data,are%20present%20at%20various%20levels.

https://dev.to/mwong068/introduction-to-linked-lists-in-ruby-kgi

<<回科普文章主選單>>