iT邦幫忙

鐵人檔案

2021 iThome 鐵人賽
回列表
自我挑戰組

從0開始啃Introduction of algorithms心得與記錄 系列

一個月的時間,從第一頁開始啃Introduction of algorithms,演算法學習記錄。

鐵人鍊成 | 共 30 篇文章 | 4 人訂閱 訂閱系列文 RSS系列文
DAY 1

Day-1 簡介與參賽動機

簡介 第一次參加鐵人賽,大家好,ID的由來為相信任何一門技術,只要投注心力,與正確的學期方向,就能夠將技術使用的,徐以杓酌油瀝之,自錢孔入,而錢不溼般的靈活自如...

DAY 2

Day-2 演算法介紹

演算法(Algorithms) 大致上來說,演算法為具有明確定義的計算過程,根據輸入得到不同的輸出,演算法就是一個將輸入變成輸出的一連串的計算過程,且須要具備五...

DAY 3

Day-3 insertion sort與循環不變式

插入排序(insertion sort) Input: 一連串正整數所成的集合 { } Output: 一連串已經過排序的正整數集合 { },且 雖然概念上...

DAY 4

Day-4 演算法分析概念

分析演算法 分析演算法,即是分析一個演算法的效率,來決定我們要使用哪一種演算法,而效率的分析方式通常會使用時間進行分析,忽略記憶體,或是頻寬之類的議題。 在分析...

DAY 5

Day-5 演算法分析工具 : 漸進式符號(Big-O, Big-Theta, Big-Omega)

前言 比較合併排序法與插入排序法,一旦輸入n的規模足夠大時,合併排序在最壞情況所需的時間Θ,而插入排序法在最壞情況所需的時間為Θ,當n足夠大時,合併排序法的效率...

DAY 6

Day-6 Divide-and-Conquer-1 : merge sort

設計演算法 我們可以選擇的演算法設計技術有很多種。插入排序使用了遞增逼近(incremental approach)的方法 : 在排序子陣列之後,將單個元素插入...

DAY 7

Day-7 Divide-and-Conquer-2 : 求解遞迴式

如何求解遞迴式 目前主要有三種方法來求解遞迴式(至今沒有任何一個好的演算法可以有效地解決遞迴式) 代換法(substitution method) 他主要遵循以...

DAY 8

Day-8 Divide-and-Conquer-3 : 二分搜尋法, 費波那契數列, Strassen’s演算法

二分搜尋法(Binary Search) 前提,在一個已經排序完成的A陣列中 Divide : 元素x和A陣列的中間元素進行比較 Conquer : 在其中一個...

DAY 9

Day-9 Divide-and-Conquer-4 : Quicksort, 隨機化Quicksort

Quicksort- Tony Hoare - 1962 和merge-sort一樣,他使用了Divide and conquer的想法,下面是對於一個陣列進行...

DAY 10

Day-10 heap與heap sort

Heap Heap(堆積)是一個陣列,可以把它看作類似完全二元樹(也就是按照順序排放的樹)。 p.s : 樹是一種資料結構,大部分的操作時間複雜度平均為樹將在後...