摘要:數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。數據對象是性質相同的數據元素的集合,是數據的一個子集。數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。
項目地址 https://github.com/m9rco/algo...
每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse簡易結構
├──Package │ ├── Sort 排序篇 │ │ ├── BubbleSort.php 冒泡排序 │ │ ├── HeapSort.php 堆排序 大根堆 │ │ ├── MBaseSort.php 基數排序 MSD │ │ ├── LBaseSort.php 基數排序 LSD │ │ ├── QuickSort.php 快速排序 │ │ ├── ShellSort.php 希爾排序 │ │ ├── MergeSort.php 歸并排序 │ │ ├── InsertSort.php 插入排序 │ │ └── SelectSort.php 選擇排序 │ │ │ ├── Query 查找篇 │ │ ├── BinaryQuery.php 二分查找 │ │ ├── InseertQuery.php 插入查找 │ │ ├── FibonacciQuery.php 斐波那契查找 │ │ └── QulickQuery.php 快速查找 │ │ │ ├── Structure 數據結構 │ │ ├── StackExample.php 堆棧 先進后出 LIFO (Last In First Out) │ │ ├── LinearChain.php 線性表 單鏈存儲 │ │ └── LinearOrder.php 線性表 順序存儲 │ │ │ ├── Tools 小工具集 │ │ └── SystemSwitch.php 堆棧實現進制轉換 │ │ │ └── Other 其他 │ ├── MonkeyKing.php 約瑟夫環 │ ├── DynamicProgramming.php 動態規劃 │ ├── Fibonacci.php 斐波那契數列 │ ├── StealingApples.php 偷蘋果求余 │ ├── HanoiGames.php 漢諾塔游戲 │ ├── BidirectionalQueue.php 雙向隊列 │ ├── ColorBricks.php 彩色磚塊 │ ├── GetCattle.php 牛年求牛 │ ├── OnlyNumbers.php 求唯一數 │ ├── PokerGames.php 洗撲克牌 │ └── BigSmallReplace.php Hello World 輸出 Olleh Dlrow │ ├──LICENSE └──README.md要做什么?
記錄自己理解算法,數據結構的過程,盡可能的簡單全面以及詳細,讓算法學習運用靈活自如,加油(? ??_??)?當然
用 PHP 實現算法并替代官方提供的函數是愚蠢的事情 .但這覺不代表斟酌算法就是件無意義的事 , 每個算法都是一種思想的結晶 , 學習優秀的思想 , 開拓思維什么是算法?
直白地說,算法就是任何明確定義的計算過程,它接收一些值或集合作為輸入,并產生一些值或集合作為輸出。這樣,算法就是將輸入轉換為輸出的一系列計算過程。來源:Thomas H. Cormen, Chales E. Leiserson (2009), 《算法導論第三版》。
簡而言之,我們可以說算法就是用來解決一個特定任務的一系列步驟(是的,不止計算機在使用算法,人類也同樣如此)。目前,一個有效的算法應該含有三個重要特性:
它必須是有限的:如果你設計的算法永無休止地嘗試解決問題,那么它是無用的。
它必須具備明確定義的指令:算法的每一步都必須準確定義,在任何場景下指令都應當沒有歧義。
它必須是有效的:一個算法被設計用以解決某個問題,那么它就應當能解決這個問題,并且僅僅使用紙和筆就能證明該算法是收斂的。
對數log10100 相當于問"降多少個10相乘的結果為100",答案當然是2個了
因此log10100=2,即對數運算是冪運算的逆運算
left | right |
---|---|
23 = 8 | log28 = 3 |
24 = 16 | log216 = 4 |
25 = 32 | log232 = 5 |
戰斗吧!少年
運行時間以二分查找為例,使用它可節省多少時間呢?簡單查找諸葛地檢查數字,如果列表包含100個數字,最多需要猜100次。
換而言之最多需要猜測的次數與列表長度相同,這被稱為線性時間(linear time),而二分查找則不同,如果列表包含100個元素
最多需要7次,如果列表包含40億個數字,最多需猜32次,而分查找的運行時間為對數時間 O(log)
大O表示法是一種特殊的表示法 ,指出了算法的速度有多快。有個屌用啊,實際上,你經常要去復制別人的代碼。
在這種情況下,知道這些算法的速度有快有慢
算法的運行時間以不同的速度增加
例如簡單查找與二分查找的區別
元素 | 簡單查找 | 二分查找 |
---|---|---|
100個元素 | 100ms | 7ms |
10000個元素 | 10s | 14ms |
1 000 000 000 個元素 | 11天 | 30ms |
大O表示發指出了算法有多快,例如列表包含n個元素,簡單查找需要檢查每個元素,因此需要執行n次操作
使用大O表示發這個運行時間為O(n),二分查找需要執行logn次操作,使用大O表示為O(log n)
一些常見的大O運行時間
O(log n) ,也叫對數時間,這樣的算法包括二分算法
O(n),也叫線性時間,這樣的算法包括簡單查找。
O(n * log n) 快速排序
O(n2),選擇排序
O(n!) 即階乘時間
這里是重點
算法的速度指的并非時間,而是操作數的增速
談論算法的速度時間時,我們說的是隨著輸入的增加,其運行時間將以什么樣的速度增加
算法的運行時間用大O表示發表示
O(log n)比O(n)快,當需要搜索的元素越多時,前者比后者快的越多
編寫解決實際問題的程序過程如何用數據形式描述問題,即將問題抽象為一個數學模型
問題所涉及到的數據量的大小及數據之間的關系
如何在計算機中儲存數據及體現數據之間的關系
處理數據時需要對數據執行的操作
編寫的程序的性能是否良好
數據(Data)是客觀事物的符號表示,在計算機科學中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。
數據元素(Data Element) :是數據的基本單位,在程序中通常作為一個整體來進行考慮和處理。一個數據元素可由若干個數據項(Data Item)組成。
數據項(Data Item) : 是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。
數據對象(Data Object) :是性質相同的數據元素的集合,是數據的一個子集。如字符集合C={‘A’,’B’,’C,…} 。
數據結構 :相互之間具有一定聯系的數據元素的集合。
數據的邏輯結構 : 數據元素之間的相互關系稱為邏輯結構。
數據操作 : 對數據要進行的運算
數據類型(Data Type):指的是一個值的集合和定義在該值集上的一組操作的總稱。
數據的邏輯結構有四種基本類型集合:結構中數據元素之間除了“屬于同一個集合"外,再也沒有其他的關系
線性結構:結構中的數據元素存在一對一的關系
樹形結構:結構中的數據元素存在一對多的關系
網狀或者圖狀結構:結構中的數據元素存在多對多的關系
數據結構的儲存方式由數據元素之間的關系在計算機中有兩種不同的表示方法——順序表示和非順序表示,從則導出兩種儲存方式,順序儲存結構和鏈式儲存結構
順序存儲結構:用數據元素在存儲器中的相對位置來表示數據元素之間的邏輯結構(關系),數據元素存放的地址是連續的
鏈式存儲結構:在每一個數據元素中增加一個存放另一個元素地址的指針(pointer),用該指針來表示數據元素之間的邏輯結構(關系),數據元素存放的地址是否連續沒有要求
數據的邏輯結構和物理結構是密不可分的兩個方面,一個算法的設計取決于所選定的邏輯結構,而算法的實現依賴于所采用的存儲結構
算法(Algorithm)是對特定問題求解方法(步驟)的一種描述,是指令的有限序列,其中每一條指令表示一個或多個操作。
算法具有以下五個特性
有窮性: 一個算法必須總是在執行有窮步之后結束,且每一步都在有窮時間內完成
確定性:算法中每一條指令必須有確切的含義,不存在二義性,且算法只有一個入口和一個出口
可行性: 一個算法是能行的,即算法描述的操作都可以通過已經實現的基本運算執行有限次來實現
輸入: 一個算法有零個或多個輸入,這些輸入取自于某個特定的對象集合
輸出: 一個算法有一個或多個輸出,這些輸出是同輸入有著某些特定關系的量
算法和程序是兩個不同的概念
一個計算機程序是對一個算法使用某種程序設計語言的具體實現。算法必須可終止意味著不是所有的計算機程序都是算法。
評價一個好的算法有以下幾個標準
正確性(Correctness ): 算法應滿足具體問題的需
可讀性(Readability): 算法應容易供人閱讀和交流,可讀性好的算法有助于對算法的理解和修改
健壯性(Robustness): 算法應具有容錯處理,當輸入非法或錯誤數據時,算法應能適當地作出反應或進行處理,而不會產生莫名其妙的輸出結果
通用性(Generality): 算法應具有一般性 ,即算法的處理結果對于一般的數據集合都成立
效率與存儲量需求: 效率指的是算法執行的時間;存儲量需求指算法執行過程中所需要的最大存儲空間,一般地,這兩者與問題的規模有關算法的時間復雜度
算法中基本操作重復執行的次數是問題規模n的某個函數,其時間量度記作T(n)=O(f(n)),稱作算法的漸近時間復雜度(Asymptotic Time complexity),簡稱時間復雜度
算法的空間復雜度是指算法編寫成程序后,在計算機中運行時所需存儲空間大小的度量,記作:S(n)=O(f(n)),其中n為問題規模
遞歸和循環的簡單比較:從程序上看,遞歸表現為自己調用自己,循環則沒有這樣的形式。
遞歸是從問題的最終目標出發,逐漸將復雜問題化為簡單問題,并且簡單的問題的解決思路和復雜問題一樣,同時存在基準情況,就能最終求得問題,是逆向的。而循環是從簡單問題出發,一步步的向前發展,最終求得問題,是正向的。
任意循環都是可以用遞歸來表示的,但是想用循環來實現遞歸(除了單向遞歸和尾遞歸),都必須引入棧結構進行壓棧出棧。
一般來說,非遞歸的效率高于遞歸。而且遞歸函數調用是有開銷的,遞歸的次數受堆棧大小的限制。
一起進步學習Fork 我的項目并提交你的 idea
Pull Request
Merge
糾錯如果大家發現有什么不對的地方,可以發起一個issue或者pull request,我會及時糾正
補充:發起pull request的commit message請參考文章Commit message 和 Change log 編寫指南致謝
感謝以下朋友的issue或pull request:
hailwood
zhangxuanru
ifreesec
openset
LicenseMIT
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/25713.html
摘要:數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。數據對象是性質相同的數據元素的集合,是數據的一個子集。數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。 項目地址 https://github.com/m9rco/algo... 每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse 簡...
摘要:數據項是數據的不可分割的最小單位。數據項是對客觀事物某一方面特性的數據描述。數據對象是性質相同的數據元素的集合,是數據的一個子集。數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。 項目地址 https://github.com/m9rco/algo... 每周最少一更,求出題,求虐待 At least once a week, ask for problems and abuse 簡...
摘要:分享一些超好用插件,打造一個不一樣的瀏覽器編輯器。一谷歌瀏覽器插件谷歌訪問助手強烈推薦一鍵安裝,無需其他配置,即可訪問谷歌。谷歌瀏覽器是很耗內存的,該插件會自動掛起長時間未使用的網頁,來釋放系統資源。 showImg(https://segmentfault.com/img/remote/1460000014011338); 分享一些超好用插件,打造一個不一樣的 GitHub、瀏覽器、...
閱讀 2878·2021-09-22 15:54
閱讀 1886·2019-08-30 15:53
閱讀 2240·2019-08-29 16:33
閱讀 1416·2019-08-29 12:29
閱讀 1387·2019-08-26 11:41
閱讀 2367·2019-08-26 11:34
閱讀 2947·2019-08-23 16:12
閱讀 1421·2019-08-23 15:56