基礎(chǔ)知識

學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法。我們要知道一些基礎(chǔ)的知識。

一、什么是算法

算法（英文algorithm）這個詞在中文里面博大精深，表示算賬的方法，也可以表示運籌帷幄的計謀等。在計算機科技里，它表示什么呢？

計算機，顧名思義是用來計算的機器。算法在計算機科學(xué)中可以描述為：計算機接收一個輸入指令，然后進行一個過程處理，最后輸出計算的結(jié)果。

這種輸入-過程處理-輸出，用人類的行為模式，很容易理解，比如媽媽讓小明去打醬油，打醬油的命令是輸入，小明發(fā)現(xiàn)小區(qū)周邊有5家店有醬油出售，娟娟超市是離家最近的，而子龍雜貨店雖然離得最遠，但醬油很便宜。小明為了省錢，跑到最遠的子龍雜貨店買了醬油，然后順利回到了家，交給了媽媽。買醬油的過程就是處理，而給媽媽的醬油是輸出。
小明為什么不去最近的娟娟超市，而去了最遠的子龍雜貨店，這是小明腦袋里思考后產(chǎn)生的最佳方案。當(dāng)然，現(xiàn)在買醬油可以通過外賣軟件，小明可以打開美團外賣軟件，搜索關(guān)鍵字：醬油，然后點擊篩選，離家最近的和最便宜的，然后選擇最便宜的醬油下單。
買醬油的過程 = 美團外賣軟件下單的過程。

人類在幾千年的演化中，會進行數(shù)字運算了，會進行利益權(quán)衡了，然后造了機器，將自己的行為模式，賦予了機器，解放了自身。如果人類真正了解人腦神經(jīng)元的信息傳遞過程，甚至可能造出有自我意識的機器，但這種場景仍然只能在科幻電影中看到。

所以，這個邏輯過程，或行為模式，在計算機里面映射的是算法。

用更準(zhǔn)確的描述來說：算法是一種有限，確定，有效的并適合用計算機程序來實現(xiàn)的，用來解決問題的方法。首先，有一個問題，然后有一個方法去解決它，這個方法叫算法。

算法是有限的，就是算法的步驟是有限的，執(zhí)行的時間也是有限的，能夠在有限時間內(nèi)得出結(jié)果。算法是確定的，就是無論執(zhí)行多少次，計算得出的結(jié)果都一樣。算法是有效的，就是計算出的結(jié)果對解決問題有幫助。

然而算法的定義一直被刷新，因為機器學(xué)習(xí)的出現(xiàn)，基于海量超大規(guī)模數(shù)據(jù)，機器學(xué)習(xí)算法的步驟是無限的，可以一直計算下去，每次計算的結(jié)果也不一樣，但如果人為進行步驟限制，以及增加訓(xùn)練閾值，訓(xùn)練時得出的參數(shù)超過設(shè)定的閾值馬上停止運算，倒也符合以上的定義。

算法要在有限的時間內(nèi)完成，本身是對人類的一種負擔(dān)，因為人類造出的機器還不夠強。為什么呢？因為即使算法的步驟是有限的，執(zhí)行的時間也可能特別長。

正如《從一到無窮大》書中印度教圣地貝拿勒斯神廟下的三根寶石針，印度教主神焚天說過，誰可以把第一根寶石針的64塊金片通過第二根寶石針移到第三根，焚天塔，神廟，婆羅門將化為灰燼，這是有名的漢諾塔算法。

漢諾塔問題可以描述為：

有三根桿(編號 A、B、C)，在 A 桿自下而上、由大到小按順序放置 64 個金盤(如下圖)。游戲的目標(biāo)：把 A 桿上的金盤全部移到 C 桿上，并仍保持原有順序疊好。

操作規(guī)則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于 A、B、C 任一桿上。

我們很自然想到一個算法：

我們必須先借助 C 桿，將 A 桿前面 N-1 個盤子，移動到 B 桿后，將 A 桿剩下的一個盤子，直接移動到 C 桿，這時候 A 空了。

然后借助 A 桿，將 B 桿的 N-1 個盤子，移動到 C 桿，任務(wù)就完成了。

十分樸素的思路，我們用編程語言來實現(xiàn)：

package mainimport "fmt"var total = 0// 漢諾塔 // 一開始A桿上有N個盤子，B和C桿都沒有盤子。 func main() {n := 4 // 64 個盤子a := "a" // 桿子Ab := "b" // 桿子Bc := "c" // 桿子Ctower(n, a, b, c)// 當(dāng) n=1 時，移動次數(shù)為 1// 當(dāng) n=2 時，移動次數(shù)為 3// 當(dāng) n=3 時，移動次數(shù)為 7// 當(dāng) n=4 時，移動次數(shù)為 15fmt.Println(total) }// 表示將N個盤子，從 a 桿，借助 b 桿移到 c 桿 func tower(n int, a, b, c string) {if n == 1 {total = total + 1fmt.Println(a, "->", c)return}tower(n-1, a, c, b)total = total + 1fmt.Println(a, "->", c)tower(n-1, b, a, c) }

通過歸納，我們可以知道移動次數(shù) Total(N) 的關(guān)系是 Total(N)=2*Total(N-1)+1，每多一個盤子，移動次數(shù)就會翻倍加一，我們通過相關(guān)的數(shù)列數(shù)學(xué)方法可以知道 Total(N)=2^N-1，也就是移動次數(shù)是一個指數(shù)方程:2的N次方,指數(shù)等于盤子的數(shù)量。

我們計算出 2^64-1=18446744073709551615，可以知道一個人日夜不停，一秒移動一次：18446744073709551615/3600/24/365/100000000=5849，要5849億年時間才可以完成這件事，那時候世界確實可能已經(jīng)毀滅。

在計算機科學(xué)中，因為所有的算法都是人定義的規(guī)則，規(guī)則是死的，所以不要擔(dān)心學(xué)不會。當(dāng)你學(xué)會了這些算法，你將會覺得，哇，一切都那么簡單。

二、什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)，顧名思義就是存放數(shù)據(jù)的結(jié)構(gòu)，也可以認為是存放數(shù)據(jù)的容器。比如，你要找出1000個數(shù)字中的最大值，首先你要將1000個數(shù)字記在某些卡片上，然后對卡片進行排序。

大多數(shù)算法都需要組織數(shù)據(jù)，所以產(chǎn)生了數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)在計算機中，主要是用來實現(xiàn)各種算法的基礎(chǔ)，當(dāng)然數(shù)據(jù)結(jié)構(gòu)本身也是算法的一部分。

基本的數(shù)據(jù)結(jié)構(gòu)有：鏈表，棧和隊列，樹和圖。

鏈表，就是把數(shù)據(jù)鏈接起來，關(guān)聯(lián)起來，一個數(shù)據(jù)節(jié)點指向另外一個數(shù)據(jù)節(jié)點，像自然界的一條條鐵鏈，大部分?jǐn)?shù)據(jù)結(jié)構(gòu)，都是由鏈表的若干變種來表示。
在每種編程語言中，數(shù)組作為基本數(shù)據(jù)類型提供，數(shù)組是連續(xù)的內(nèi)存存儲空間，通過下標(biāo)0，1，2可以迅速獲取到數(shù)組指定位置的數(shù)據(jù)。鏈表也可以用數(shù)組來實現(xiàn)，但一般情況下，因為數(shù)組是連續(xù)的，在鏈表增加和刪除節(jié)點時容易造成冗余，效果不佳。所以鏈表在不同編程語言實現(xiàn)是這樣的： C、C++ 是用指針來實現(xiàn)的，Java 是用類來實現(xiàn)的，而 Golang 是用結(jié)構(gòu)體引用來實現(xiàn)。
棧和隊列，主要用來存儲多個數(shù)據(jù)，只不過一個是先進后出，一個先進先出。比如下壓棧，先入棧的數(shù)據(jù)是最后才能出來，而我們熟知的隊列，先排隊的人肯定先獲得服務(wù)。
其次是樹和圖，樹就是有一個樹根節(jié)點，存放著數(shù)據(jù)，下面有很多子節(jié)點，也存放著數(shù)據(jù)，類比自然界的樹。圖則可以類比自然界的地圖，多個點指向多個點，點和點之間有一條或多條邊，而這些點存放著數(shù)據(jù)，邊也可以存放著數(shù)據(jù)，比如距離等。

圍繞這幾種數(shù)據(jù)結(jié)構(gòu)，有若干延伸，加上一些排序，查找邏輯，就形成了更高層次的高級數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)是算法實現(xiàn)的輔助，是為了更高效組織數(shù)據(jù)的結(jié)構(gòu)，所以數(shù)據(jù)結(jié)構(gòu)和算法其實密切聯(lián)系，并不需要分得太清，大家可以把數(shù)據(jù)結(jié)構(gòu)等同于算法。

三、什么叫好的數(shù)據(jù)結(jié)構(gòu)和好的算法

學(xué)習(xí)算法的原因，是好的算法可以節(jié)約資源，但是選擇合適的算法很難。我們要進行復(fù)雜的數(shù)學(xué)分析才能知道，什么叫做好的，在計算機里，我們把這種數(shù)學(xué)分析這叫做算法分析。

什么是好的數(shù)據(jù)結(jié)構(gòu)和好的算法？

計算機資源是有限 的，所以占用計算機資源越少的數(shù)據(jù)結(jié)構(gòu)和算法越好。

人的生命是有限的 的，等待時間是有忍耐度的，所以能輔助程序越快完成工作的數(shù)據(jù)結(jié)構(gòu)和算法越好。

所以出了個理論：時間和空間算法復(fù)雜度理論。

程序執(zhí)行過程中，要么空間換時間，要么時間換空間，空間可以認為是一種計算機資源如內(nèi)存使用情況，而時間是人類感知的第四個維度，就是慢還是快，兩者一般不能兼得，如果發(fā)現(xiàn)居然兼得了，那就是發(fā)明了一種更好的算法。

在計算機科學(xué)發(fā)展的四五十年，這種既省資源又省時間的發(fā)明還是比較少的，比如數(shù)據(jù)壓縮算法，因為發(fā)明了超高效的無損數(shù)據(jù)壓縮算法，我們網(wǎng)上看視頻的時候，既不失真，也不卡頓，又快又好，這種就叫好算法。

目前有一種新型的計算方式正在研究中，叫量子計算，可以在非常小的空間，使用非常少的資源，短時間內(nèi)計算超級大量的數(shù)據(jù)，讓我們期待能成功量產(chǎn)的那天，到了那時候，人類生產(chǎn)力將極大被解放。

四、總結(jié)

程序設(shè)計在一般程度上，很多人都認為=數(shù)據(jù)結(jié)構(gòu)+算法。

我們學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法，是為了更高效率寫出更快，更好的代碼。

因為學(xué)習(xí)過，所以我們不需要從零開始設(shè)計，工作效率就提高了。

因為知道每種數(shù)據(jù)結(jié)構(gòu)和算法的復(fù)雜度和適用場景，自由選擇組合，我們寫出的代碼計算速度變快了，占用的資源更少了。

所以我們要好好學(xué)習(xí)和理解常見的數(shù)據(jù)結(jié)構(gòu)和算法。

歡迎閱讀剩下的章節(jié)。

系列文章入口

我是陳星星，歡迎閱讀我親自寫的 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))，文章首發(fā)于

目錄 · 數(shù)據(jù)結(jié)構(gòu)和算法（Golang實現(xiàn)）?goa.lenggirl.com

• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(1)簡單入門Golang-前言
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(2)簡單入門Golang-包、變量和函數(shù)
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(3)簡單入門Golang-流程控制語句
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(4)簡單入門Golang-結(jié)構(gòu)體和方法
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(5)簡單入門Golang-接口
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(6)簡單入門Golang-并發(fā)、協(xié)程和信道
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(7)簡單入門Golang-標(biāo)準(zhǔn)庫
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(8.1)基礎(chǔ)知識-前言
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(8.2)基礎(chǔ)知識-分治法和遞歸
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(9)基礎(chǔ)知識-算法復(fù)雜度及漸進符號
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(10)基礎(chǔ)知識-算法復(fù)雜度主方法
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(11)常見數(shù)據(jù)結(jié)構(gòu)-前言
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(12)常見數(shù)據(jù)結(jié)構(gòu)-鏈表
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(13)常見數(shù)據(jù)結(jié)構(gòu)-可變長數(shù)組
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(14)常見數(shù)據(jù)結(jié)構(gòu)-棧和隊列
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(15)常見數(shù)據(jù)結(jié)構(gòu)-列表
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(16)常見數(shù)據(jù)結(jié)構(gòu)-字典
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(17)常見數(shù)據(jù)結(jié)構(gòu)-樹
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(18)排序算法-前言
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(19)排序算法-冒泡排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(20)排序算法-選擇排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(21)排序算法-插入排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(22)排序算法-希爾排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(23)排序算法-歸并排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(24)排序算法-優(yōu)先隊列及堆排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(25)排序算法-快速排序
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(26)查找算法-哈希表
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(27)查找算法-二叉查找樹
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(28)查找算法-AVL樹
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(29)查找算法-2-3樹和左傾紅黑樹
• 數(shù)據(jù)結(jié)構(gòu)和算法(Golang實現(xiàn))(30)查找算法-2-3-4樹和普通紅黑樹

總結(jié)

以上是生活随笔為你收集整理的vrp 节约算法 c++_数据结构和算法(Golang实现)(8.1)基础知识-前言的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。