簡易結(jié)構(gòu)

要做什么？

image.png

10年架構(gòu)師領(lǐng)你架構(gòu)-成長之路-（附面試題（含答案））

（騰訊T3-T4）打造互聯(lián)網(wǎng)PHP架構(gòu)師教程目錄大全，只要你看完，薪資立馬提升2倍（持續(xù)更新）

點擊與我交流企鵝群.

原文轉(zhuǎn)發(fā)：segmentfault.com

當(dāng)然

用 PHP 實現(xiàn)算法并替代官方提供的函數(shù)是愚蠢的事情 .但這覺不代表斟酌算法就是件無意義的事 , 每個算法都是一種思想的結(jié)晶 , 學(xué)習(xí)優(yōu)秀的思想 , 開拓思維

什么是算法？

直白地說，算法就是任何明確定義的計算過程，它接收一些值或集合作為輸入，并產(chǎn)生一些值或集合作為輸出。這樣，算法就是將輸入轉(zhuǎn)換為輸出的一系列計算過程。來源：Thomas H. Cormen, Chales E. Leiserson (2009), 《算法導(dǎo)論第三版》。

簡而言之，我們可以說算法就是用來解決一個特定任務(wù)的一系列步驟（是的，不止計算機在使用算法，人類也同樣如此）。目前，一個有效的算法應(yīng)該含有三個重要特性：

• 它必須是有限的：如果你設(shè)計的算法永無休止地嘗試解決問題，那么它是無用的。

• 它必須具備明確定義的指令：算法的每一步都必須準(zhǔn)確定義，在任何場景下指令都應(yīng)當(dāng)沒有歧義。

• 它必須是有效的：一個算法被設(shè)計用以解決某個問題，那么它就應(yīng)當(dāng)能解決這個問題，并且僅僅使用紙和筆就能證明該算法是收斂的。

對數(shù)

log10100 相當(dāng)于問"降多少個10相乘的結(jié)果為100"，答案當(dāng)然是2個了 因此log10100=2，即對數(shù)運算是冪運算的逆運算

image

運行時間

以二分查找為例，使用它可節(jié)省多少時間呢？簡單查找諸葛地檢查數(shù)字，如果列表包含100個數(shù)字，最多需要猜100次。 換而言之最多需要猜測的次數(shù)與列表長度相同，這被稱為線性時間(linear time)，而二分查找則不同，如果列表包含100個元素 最多需要7次，如果列表包含40億個數(shù)字，最多需猜32次，而分查找的運行時間為對數(shù)時間 O(log)

大O表示法

大O表示法是一種特殊的表示法 ，指出了算法的速度有多快。有個屌用啊，實際上，你經(jīng)常要去復(fù)制別人的代碼。 在這種情況下，知道這些算法的速度有快有慢

• 算法的運行時間以不同的速度增加

• 例如簡單查找與二分查找的區(qū)別

image

• 大O表示發(fā)指出了算法有多快，例如列表包含n個元素，簡單查找需要檢查每個元素，因此需要執(zhí)行n次操作 使用大O表示發(fā)這個運行時間為O(n),二分查找需要執(zhí)行l(wèi)ogn次操作，使用大O表示為O(log n)

點擊與我交流企鵝群.

感謝大家一直來支持，這是我準(zhǔn)備的1000粉絲福利

【1000粉絲福利】10年架構(gòu)師分享PHP進階架構(gòu)資料，助力大家都能30K

• 一些常見的大O運行時間

• O(log n) ,也叫對數(shù)時間，這樣的算法包括二分算法

• O(n),也叫線性時間，這樣的算法包括簡單查找。

• O(n * log n) 快速排序

• O(n2),選擇排序

• O(n!) 即階乘時間

• 這里是重點

• 算法的速度指的并非時間，而是操作數(shù)的增速

• 談?wù)撍惴ǖ乃俣葧r間時，我們說的是隨著輸入的增加，其運行時間將以什么樣的速度增加

• 算法的運行時間用大O表示發(fā)表示

• O(log n)比O(n)快，當(dāng)需要搜索的元素越多時，前者比后者快的越多

編寫解決實際問題的程序過程

• 如何用數(shù)據(jù)形式描述問題，即將問題抽象為一個數(shù)學(xué)模型

• 問題所涉及到的數(shù)據(jù)量的大小及數(shù)據(jù)之間的關(guān)系

• 如何在計算機中儲存數(shù)據(jù)及體現(xiàn)數(shù)據(jù)之間的關(guān)系

• 處理數(shù)據(jù)時需要對數(shù)據(jù)執(zhí)行的操作

• 編寫的程序的性能是否良好

數(shù)據(jù)(Data)

• 是客觀事物的符號表示，在計算機科學(xué)中指的是所有能輸入到計算機中并被計算機程序處理的符號的總稱。

• 數(shù)據(jù)元素(Data Element) :是數(shù)據(jù)的基本單位，在程序中通常作為一個整體來進行考慮和處理。一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項(Data Item)組成。

• 數(shù)據(jù)項(Data Item) : 是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)項是對客觀事物某一方面特性的數(shù)據(jù)描述。

• 數(shù)據(jù)對象(Data Object) :是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。如字符集合C={‘A’,’B’,’C,…} 。

• 數(shù)據(jù)結(jié)構(gòu) :相互之間具有一定聯(lián)系的數(shù)據(jù)元素的集合。

• 數(shù)據(jù)的邏輯結(jié)構(gòu) : 數(shù)據(jù)元素之間的相互關(guān)系稱為邏輯結(jié)構(gòu)。

• 數(shù)據(jù)操作 : 對數(shù)據(jù)要進行的運算

• 數(shù)據(jù)類型(Data Type):指的是一個值的集合和定義在該值集上的一組操作的總稱。

大廠2000道面試題（含答案）

PHP面試題匯總，看完這些面試題助力你面試成功，工資必有20-25K

點擊與我交流企鵝群.

數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本類型

• 集合：結(jié)構(gòu)中數(shù)據(jù)元素之間除了“屬于同一個集合"外,再也沒有其他的關(guān)系

• 線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系

• 樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系

• 網(wǎng)狀或者圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系

數(shù)據(jù)結(jié)構(gòu)的儲存方式

由數(shù)據(jù)元素之間的關(guān)系在計算機中有兩種不同的表示方法——順序表示和非順序表示，從則導(dǎo)出兩種儲存方式，順序儲存結(jié)構(gòu)和鏈?zhǔn)絻Υ娼Y(jié)構(gòu)

• 順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)，數(shù)據(jù)元素存放的地址是連續(xù)的

• 鏈?zhǔn)酱鎯Y(jié)構(gòu)：在每一個數(shù)據(jù)元素中增加一個存放另一個元素地址的指針(pointer)，用該指針來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)(關(guān)系)，數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求

數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是密不可分的兩個方面，一個算法的設(shè)計取決于所選定的邏輯結(jié)構(gòu)，而算法的實現(xiàn)依賴于所采用的存儲結(jié)構(gòu)

算法(Algorithm)

是對特定問題求解方法(步驟)的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。

算法具有以下五個特性

• 有窮性： 一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成

• 確定性：算法中每一條指令必須有確切的含義，不存在二義性，且算法只有一個入口和一個出口

• 可行性： 一個算法是能行的，即算法描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)

• 輸入： 一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合

• 輸出： 一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關(guān)系的量

算法和程序是兩個不同的概念

一個計算機程序是對一個算法使用某種程序設(shè)計語言的具體實現(xiàn)。算法必須可終止意味著不是所有的計算機程序都是算法。

評價一個好的算法有以下幾個標(biāo)準(zhǔn)

• 正確性(Correctness )： 算法應(yīng)滿足具體問題的需

• 可讀性(Readability)： 算法應(yīng)容易供人閱讀和交流，可讀性好的算法有助于對算法的理解和修改

• 健壯性(Robustness)： 算法應(yīng)具有容錯處理，當(dāng)輸入非法或錯誤數(shù)據(jù)時，算法應(yīng)能適當(dāng)?shù)刈鞒龇磻?yīng)或進行處理，而不會產(chǎn)生莫名其妙的輸出結(jié)果

• 通用性(Generality)： 算法應(yīng)具有一般性 ，即算法的處理結(jié)果對于一般的數(shù)據(jù)集合都成立

效率與存儲量需求： 效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間，一般地，這兩者與問題的規(guī)模有關(guān)

算法的時間復(fù)雜度

算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，其時間量度記作T(n)=O(f(n))，稱作算法的漸近時間復(fù)雜度(Asymptotic Time complexity)，簡稱時間復(fù)雜度

算法的空間復(fù)雜度

是指算法編寫成程序后，在計算機中運行時所需存儲空間大小的度量，記作：S(n)=O(f(n)),其中n為問題規(guī)模

遞歸和循環(huán)的簡單比較：

1. 從程序上看，遞歸表現(xiàn)為自己調(diào)用自己，循環(huán)則沒有這樣的形式。

2. 遞歸是從問題的最終目標(biāo)出發(fā)，逐漸將復(fù)雜問題化為簡單問題，并且簡單的問題的解決思路和復(fù)雜問題一樣，同時存在基準(zhǔn)情況，就能最終求得問題，是逆向的。而循環(huán)是從簡單問題出發(fā)，一步步的向前發(fā)展，最終求得問題，是正向的。

3. 任意循環(huán)都是可以用遞歸來表示的，但是想用循環(huán)來實現(xiàn)遞歸（除了單向遞歸和尾遞歸），都必須引入棧結(jié)構(gòu)進行壓棧出棧。

4. 一般來說，非遞歸的效率高于遞歸。而且遞歸函數(shù)調(diào)用是有開銷的，遞歸的次數(shù)受堆棧大小的限制。

一起進步學(xué)習(xí)

1. Fork 我的項目并提交你的 idea

2. Pull Request

3. Merge

糾錯

如果大家發(fā)現(xiàn)有什么不對的地方，可以發(fā)起一個issue或者pull request,我會及時糾正

補充:發(fā)起pull request的commit message請參考文章Commit message 和 Change log 編寫指南。

喜歡我的文章就關(guān)注我吧，持續(xù)更新中.....

以上內(nèi)容希望幫助到大家，很多PHPer在進階的時候總會遇到一些問題和瓶頸，業(yè)務(wù)代碼寫多了沒有方向感，不知道該從那里入手去提升，對此我整理了一些資料，包括但不限于：分布式架構(gòu)、高可擴展、高性能、高并發(fā)、服務(wù)器性能調(diào)優(yōu)、TP6，laravel，YII2，Redis，Swoole、Swoft、Kafka、Mysql優(yōu)化、shell腳本、Docker、微服務(wù)、Nginx等多個知識點高級進階干貨需要的可以免費分享給大家，需要的可以點擊進入暗號：知乎。