演算法與資料結構介紹演算法與資料結構的基本概念。 Show
Complexity系列文章Complexity：Asymptotic Notation(漸進符號) 基本資料結構系列文章Linked ListLinked List：Intro(簡介) StackStack：Intro(簡介) QueueQueue：Intro(簡介)，並以Linked list實作 SetSet：以Array表示 Sort系列文章Comparison SortComparison Sort：Insertion Sort(插入排序法) Tree系列文章Tree(樹)：Intro(簡介) Binary Tree(二元樹)Binary Tree：Intro(簡介) Binary Search Tree(二元搜尋樹)Binary Search Tree：Intro(簡介) Red Black Tree(紅黑樹)Red Black Tree：Intro(簡介) Hash Table系列文章Hash Table：Intro(簡介) Graph系列文章Graph：Intro(簡介) Breadth-First Search與Depth-First SearchGraph：Breadth-First Search(BFS，廣度優先搜尋) Minimum Spanning Tree(最小生成樹)Minimum Spanning Tree：Intro(簡介) Shortest PathShortest Path：Intro(簡介) Flow NetworksFlow Networks：Maximum Flow & Ford-Fulkerson Algorithm Priority Queue系列文章Priority Queue：Intro(簡介) 基礎演算法與資料結構學習筆記基礎演算法與資料結構，常常是工作後沒在用就很容易忘記，但面試又很愛考，每次要準備面試前都要重新搜集資料複習，這次就趁有時間時候，一邊複習一邊紀錄一下這次基礎演算法與資料結構的學習筆記。 基礎演算法系列Sort基礎演算法系列 — 你只會用 built-in function 來排序嗎？在演算法學習中，排序大概是最基本的一類演算法了，大學時候的演算法課程可能前幾章就會教到。但是工作以後，排序這種東西除非有特殊需求，不然通常都是用 built-in function…medium.com Search基礎演算法系列 — 該怎麼搜尋之Search演算法Search 搜尋，這也是演算法之中基礎的基礎，主要想要解決的問題是，在一個已排序或是未排序的序列中，找到目標的元素。其實平常沒在複習，工作上也是直接用 built-in function，除了直觀的 Sequential Search…medium.com Tree基礎演算法系列 — Tree 樹狀資料結構在資料結構中，「Tree」與「Graph」是兩個重要的資料結構，許多實務上系統的應用與開發，底層都跟他們脫不了關係，像是資料儲存、HTML DOM Tree 或甚至是組織架構圖都會用到 Tree 的概念。本篇筆記以 Tree…medium.com Linked-list and Array基礎演算法系列 — 基礎資料結構 Linked-list 與 ArrayLinked List 與 Array 是最常拿來比較，也是兩種基本的資料結構，它們都可以用來儲存資料，但是在使用情境不同的情況下，使用 Linked List 或是Array 都會有著各自不同的好處與壞處。medium.com Graph基礎演算法系列 — Graph 資料結構與Dijkstra’s AlgorithmGraph，在資料結構中也是一個基礎且非常重要的一個資料結構，用於表示物體與物體之間存在某種關係的結構。定義中，會由點(物體)與線(物體間的關係)，來描繪出一個 Graph，如下圖就是一個簡單的 Graph：medium.com 演算法筆記系列Two Pointer and Sliding Window演算法筆記系列 — Two Pointer 與Sliding WindowTwo Pointer 與 Sliding Window 都是蠻常聽到的一種解題常用的技巧，也可以說是演算法的解題 pattern。而 Two Pointer 又可以分為左右指標與快慢指標兩種，Sliding Window…medium.com Dynamic programming演算法筆記系列 — Dynamic programming 動態規劃Dynamic Programming 動態規劃，通常會簡稱作為 DP，是一個在解題很常用的一種解題方式，原理是透過把原問題分解為相對簡單的子問題的方式，來求解複雜問題的方法。
medium.com Monotonic Stack/Queue演算法筆記系列 — Monotonic Stack/Queue在資料結構中， Stack/Queue 是一般來說比較廣為人知的基礎資料結構，而你知道還有一種變化型的 Monotonic Stack/Queue 嗎？這個資料結構也是在寫 leetcode…medium.com 程式語言Pascal的創建者曾經說過：「演算法+資料結構=程式」，事實上，演算法往往決定了該如何解決問題的大方向，至於我們對於資料結構的選擇，則決定了實作程式的難易度。 演算法與資料結構 基本上，資料結構描述的是（電腦中）儲存、組織資料的方式，而演算法規範的是一系列運算步驟，並不涉及特定程式語言（甚至是不涉及電腦的運用），因而我們可以使用虛擬碼、流程圖，或甚至自然語言來描述。 演算法當中雖然討論空間複雜度，不過，嚴格來說，演算法並不涉及特定資料結構，只不過在存取特定資料結構時，確實也需要一系列的運算步驟，而這類步驟，就是為了解決特定資料結構組織、存取資料時的演算法。 雖然演算法與資料結構是兩個不同的研究領域，然而，實際上，選擇不同的資料結構，會影響存取該資料結構的演算方式，而存取資料結構的演算方式，其實是會影響程式主要演算法實作上的難易度、效率等問題。 正確的資料結構也可以提高程式主要演算法的效率，而有些資料結構更是為了解決特定問題而設計，兩者其實是相輔相成。 舉例來說，想要創建迷宮，我們可以使用遞迴回溯演算，若要運用這演算並不需要電腦，只使用紙筆，也可以實現遞迴回溯演算來手繪迷宮，簡單來說，四個方向隨機選一個鄰居細胞，若下個細胞未造訪過，打通該面牆、走到下個細胞，若沒有可造訪的細胞就原路返回，重複以上流程、直到全部細胞都造訪過為止。 若是方形迷宮，程式實作上很自然地，會選擇二維陣列之類的資料結構，因為上下左右的選擇，在演算法上只是行（column）、列（row）索引加或減一的關係，無論是索引存取或行、列索引計算，二維陣列都是適合方形迷宮的資料結構，也適於實現遞迴回溯演算。 如果想實現其他形狀的迷宮，我在先前專欄〈從節點編碼看迷宮〉中，所談過的遮罩迷宮、蜂巢狀迷宮、圓柱迷宮，甚至是基於迷宮的哈密頓路徑等，其實，也都可以基於二維陣列來實現。不過，如果是圓形迷宮呢？ 從方形到圓形 如果想做個圓形迷宮，方式之一是透過遮罩，圓範圍外的全部細胞設為已走訪，我們只走訪圓範圍內的細胞，只不過這有點投機取巧。 實際上，圓範圍內的細胞，還是以行列的方式繪製，而我們在這邊想要製作的圓形迷宮，細胞必須是同心圓式的排列，至於這類迷宮又常俗稱為Theta迷宮。 我在〈從節點編碼看迷宮〉中談過，可以基於二維陣列、遞迴回溯演算來走訪細胞，只要在繪圖上做些變化，就能實現蜂巢狀迷宮，那麼，如果我們單純將細胞繪製為同心圓排列，是否就能實現Theta迷宮？ 基本上，這是可行的，我們只要將列索引當成環索引，行索引當成逆時針方向索引，以極座標方式繪製。而關於這樣的概念，我們可以在〈Theta 迷宮（一）〉看到具體實現方式。 只不過，若運用這種方式來處理，越外環的迷宮道路會有開口越大的問題，畢竟只是純粹將方形拉成圓形罷了，雖然這也可以是迷宮的一種風格，不過若想避免這個問題，就必須決定在某個環數之後切分細胞，而在這樣的情況下，依舊可以使用遞迴回溯演算，只不過往外環選擇鄰居細胞時，某些環上會是二選一罷了，然而，這意謂著，各環的細胞數可能不同，也就是不再能從m列n行的迷宮來變換，單純採用二維陣列作為細胞的資料結構，顯然行不通了。 這問題長年以來困擾著我，後來想到的方式是改變資料結構，改採一維陣列，此時，陣列中僅加入走訪過的細胞，而細胞的逆時針座標可由最外環的細胞數來決定，座標的步進值則看是位於哪一環，而在計算時，最簡單的作法是每兩環切分一次細胞，若環索引是從0開始，就是在每個偶數環時進行切分。 然而，每兩環切分一次細胞，雖然解決了越外開口越大的問題，卻也造成了越外環細胞越小的問題，而且這可是二的n次方在增長，只要八環左右，細胞就會密到不像話了。 如果想要改善上述的狀況，我們可以試著改為兩環一切、三環一切、四環一切……不過，這在計算上就變得更為複雜了，而且，也只是減緩細胞過快變小的問題罷了，關於實作細節部份，我們可以參考〈Theta 迷宮（二）〉的內容。 鏈結各個細胞 想要更進一步解決這個問題，依圓周長決定將細胞一切為二的時機，顯然會是一個比較好的作法，然而，這就直接面臨了逆時針座標計算上的難度。這不禁讓我重新思考，到底是資料結構選擇的問題？還是遞迴回溯演算的問題？ 我在紙上計算著細胞的逆時針座標時，不經意地在細胞間畫了線連起來，突然想到：「如果細胞彼此間採鏈結（link）結構組織呢？」 每個細胞記得自身的（內環）父細胞、順時針、逆時針與（外環）子細胞的話，就不用計算逆時針座標了，直接查詢細胞鏈結的細胞就可以了，而且改變資料結構，依舊可以使用遞迴回溯演算，實作細節部份可以參考〈Theta 迷宮（三）〉的內容。 實際上，依圓周長決定選擇將細胞一切為二的時機，外環細胞還是會變小，只是收斂地很慢，然而，實現時可以留個權重參數，讓使用者能根據需要的迷宮大小，來調整對分的時機，而這就足以應付百環以上的Theta迷宮問題了（只要硬體或執行環境上能支援）。 這時的我才驚覺，長年以來解決不了的問題，是因為採用了不適合的資料結構，又試著強行從中尋找解決方式造成的。 實際上，採用鏈結作為資料結構，也適用於方形迷宮，不過這是需求與設計間平衡的問題，若只是要方形迷宮，二維陣列還是最好的選擇，畢竟只要處理列、行索引加減一的問題，採用鏈結的話，可能還會覺得多此一舉。 然而，如果一開始就是想使用遞迴回溯演算，並用同一個程式作為通用實作，可同時處理方形迷宮與Theta迷宮的問題，那麼，一開始就採用鏈結作為資料結構的實作方式，就會有價值。 演算法+資料結構=程式 其實，在試著從二維陣列改為一維陣列，實作出Theta迷宮時，我第一個想到的，就是Pascal創建者Niklaus E. Writh講過的這句話：「演算法+資料結構=程式（Algorithms+Data Structures=Programs）」。 而在試著更改資料結構為鏈結，實現了依圓周長而切分細胞的程式時，我更是進一步體會到：資料結構選擇的適當與否，真的是一件重要的工作。 原來，我自己一直被資料結構框住了想法，而不自覺。或許我也應該從另一個角度來探索看看，思考一下其他的迷宮演算法，是否對實作Theta迷宮有利呢！ |
資料 結構 演算 法
版權 © 2024 zh.apacode Inc.
