計(jì)算機(jī)算法核心知識(shí)點(diǎn)梳理個(gè)人學(xué)習(xí)筆記基礎(chǔ) 高頻考點(diǎn)目錄第一章 緒論1.1 什么是算法1.2 算法的描述1.3 算法的分析1.4重要的問題類型第2章 算法效率分析基礎(chǔ)第3章 蠻力法3.1 選擇排序和冒泡排序3.1.1選擇排序3.1.2 冒泡排序3.2 順序查找和蠻力字符串匹配3.2.1 順序查找3.2.2蠻力字符串匹配3.3 最近對(duì)和凸包問題的蠻力算法3.3.1 最近問題3.3.2 凸包問題3.4 窮舉查找3.5深度優(yōu)先查找和廣度優(yōu)先查找3.5.1 深度優(yōu)先查找3.5.2 廣度優(yōu)先查找第4章 減治法4.1 插入排序4.2 拓?fù)渑判?.3生成祝賀對(duì)象的算法4.4 減常因子算法4.4.1 折半查找4.4.2 假幣問題4.4.3 俄式乘法4.4.4 約瑟夫斯問題4.5減可變規(guī)模算法4.5.1 插值查找第五章 分治法5.1 合并排序5.2 快速排序第一章 緒論1.1 什么是算法算法(algorithm)是一系列解決問題的明確指令也就是說對(duì)于符合一定規(guī)范的輸入能夠在有限時(shí)間內(nèi)獲得要求的輸出。觀點(diǎn)可以認(rèn)為算法是問題的程序化解決方案。1.2 算法的描述偽代碼(pseudocode)是自然語言和類編程語言組成的混合結(jié)構(gòu)。偽代碼往往比自然語言更精確而且用偽代碼描述的算法往往會(huì)更簡潔。用箭頭代表賦值操作。1.3 算法的分析效率有兩種時(shí)間效率(time efficiency),指出算法運(yùn)行有多快。空間效率(space efficiency),說明算法需要多少額外的存儲(chǔ)空間。1.4重要的問題類型排序問題(sorting problem)要求我們按照升序重新排列給定列表中的數(shù)據(jù)項(xiàng)。查找問題(searching problem)就是在給定的集合或者是多重集它允許多個(gè)元素具有相同的值)中找一個(gè)給定的值[我們稱之為查找鍵(search key)]。字符串處理也稱字符串匹配問題圖問題組合問題幾何問題類似于點(diǎn)、線、多面體這樣的幾何對(duì)象。數(shù)值問題(numerical problem)是另一個(gè)廣闊的具體應(yīng)用領(lǐng)域涉及具有連續(xù)性的數(shù)學(xué)問題像解方程和方程組計(jì)算定積分以及求函數(shù)的值等。第2章 算法效率分析基礎(chǔ)不做筆記第3章 蠻力法蠻力法(brute force)是一種簡單直接地解決問題的方法常常直接基于問題的描述和所涉及的概念定義。3.1 選擇排序和冒泡排序3.1.1選擇排序3.1.2 冒泡排序3.2 順序查找和蠻力字符串匹配3.2.1 順序查找該算法只是簡單地將給定列表中的連續(xù)元素和給定的查找鍵進(jìn)行比較直到遇到一個(gè)匹配的元素成功查找或者在遇到匹配元素前就遍歷了整個(gè)列表失敗查找)。實(shí)現(xiàn)順序查找時(shí)常常會(huì)使用這樣一個(gè)小技巧如果我們把查找鍵添加到列表的末尾那么查找就一定會(huì)成功所以不必在算法的每次循環(huán)時(shí)都檢查是否到達(dá)了表的末尾。以下是這個(gè)增強(qiáng)版本的偽代碼。3.2.2蠻力字符串匹配查找字符串第一個(gè)字符的位置請(qǐng)注意在這個(gè)例子中幾乎每做一次字符比較就要移動(dòng)一次模式的位置。然而最壞的情況比這還要糟得多在移動(dòng)模式之前算法可能會(huì)做足m次比較而n-m1次嘗試的每一次都可能會(huì)遇到這種情況。因此在最壞的情況下該算法屬于O(nm)。3.3 最近對(duì)和凸包問題的蠻力算法3.3.1 最近問題最近點(diǎn)對(duì)問題要求在一個(gè)包含n個(gè)點(diǎn)的集合中找出距離最近的兩個(gè)點(diǎn)。這種處理平面或者高維空間的鄰近點(diǎn)的問題在各種計(jì)算幾何問題當(dāng)中是最簡單的。最近點(diǎn)對(duì)問題的一個(gè)最重要的應(yīng)用是統(tǒng)計(jì)學(xué)中的聚類分析。3.3.2 凸包問題在平面或者高維空間的一個(gè)給定點(diǎn)集合中尋找凸包被視為計(jì)算幾何中最重要的問題之一。定義對(duì)于平面上的一個(gè)點(diǎn)集合有限的或無限的如果以集合中任意兩點(diǎn)p和q為端點(diǎn)的線段都屬于該集合我們說這個(gè)集合是凸的。凸包問題省略3.4 窮舉查找對(duì)于組合問題來說窮舉查找(exhaustive search)是一種簡單的蠻力方法。它要求生成問題域中的每一個(gè)元素選出其中滿足問題約束的元素然后再找出一個(gè)期望元素例如使目標(biāo)函數(shù)達(dá)到最優(yōu)的元素)。注意雖然窮舉查找的思想很簡單直接但在實(shí)現(xiàn)時(shí)它常常會(huì)要求算法來生成某些組合對(duì)象。常見問題旅行商問題背包問題分配問題3.5深度優(yōu)先查找和廣度優(yōu)先查找3.5.1 深度優(yōu)先查找深度優(yōu)先查找可以從任意頂點(diǎn)開始訪問圖的頂點(diǎn)然后把該頂點(diǎn)標(biāo)記為已訪問。在每次迭代的時(shí)候該算法緊接著處理與當(dāng)前頂點(diǎn)鄰接的未訪問頂點(diǎn)。如果有若干個(gè)這樣的頂點(diǎn)可以任意選擇一個(gè)頂點(diǎn)。但在實(shí)際應(yīng)用中選擇哪一個(gè)鄰接的未訪問候選頂點(diǎn)主要是由表示圖的數(shù)據(jù)結(jié)構(gòu)決定的。在我們的例子中我們總是根據(jù)頂點(diǎn)的字母順序來選擇頂點(diǎn)。)這個(gè)過程一直持續(xù)直到遇到一個(gè)終點(diǎn)一該頂點(diǎn)的所有鄰接頂點(diǎn)都已被訪問過。在該終點(diǎn)上該算法沿著來路后退一條邊并試著繼續(xù)從那里訪問未訪問的頂點(diǎn)。在后退到起始頂點(diǎn)并且起始頂點(diǎn)也是一個(gè)終點(diǎn)時(shí)該算法最終停了下來。這樣起始頂點(diǎn)所在的連通分量的所有頂點(diǎn)都被訪問過了。如果未訪問過的頂點(diǎn)仍然存在該算法必須從其中任一頂點(diǎn)開始重復(fù)上述過程。用一個(gè)棧來跟蹤深度優(yōu)先查找的操作是比較方便的。在第一次訪問一個(gè)頂點(diǎn)時(shí)也就是說開始對(duì)該頂點(diǎn)的訪問時(shí))我們把該頂點(diǎn)入棧當(dāng)它成為一個(gè)終點(diǎn)時(shí)也就是說結(jié)束對(duì)該頂點(diǎn)的訪問時(shí))我們把它出棧。深度優(yōu)先查找樹depth-first search forest3.5.2 廣度優(yōu)先查找按照一種同心圓的方式首先訪問所有和初始頂點(diǎn)鄰接的頂點(diǎn)然后是離它兩條邊的所有未訪問頂點(diǎn)以此類推直到所有與初始頂點(diǎn)同在一個(gè)連通分量中的頂點(diǎn)都訪問過了為止。如果仍然存在未被訪問的頂點(diǎn)該算法必須從圖的其他連通分量中的任意頂點(diǎn)重新開始。使用隊(duì)列注意它和深度優(yōu)先查找的區(qū)別來跟蹤廣度優(yōu)先查找的操作是比較方便的。該隊(duì)列先從遍歷的初始頂點(diǎn)開始將該頂點(diǎn)標(biāo)記為已訪問。在每次迭代的時(shí)候該算法找出所有和隊(duì)頭頂點(diǎn)鄰接的未訪問頂點(diǎn)把它們標(biāo)記為已訪問再把它們?nèi)腙?duì)。然后將隊(duì)頭頂點(diǎn)從隊(duì)列中移去。廣度優(yōu)先查找森林breadth-first search forcest第4章 減治法4.1 插入排序我們考慮如何用減一技術(shù)對(duì)一個(gè)數(shù)組A[0.-1]排序。遵循該方法的思路我們假設(shè)對(duì)較小數(shù)組A[0.n-2]排序的問題已經(jīng)解決了得到了一個(gè)大小為n-1的有序數(shù)組A0]≤…≤[n-2]。我們?nèi)绾卫眠@個(gè)較小規(guī)模的解并將元素A[n-1]考慮進(jìn)來來得到原問題的解呢顯然我們需要做的就是在這些有序的元素中為A[-1]找到一個(gè)合適的位置然后把它插入到那里。一般來說我們可以從右到左掃描這個(gè)有序的子數(shù)組直到遇到第一個(gè)小于等于A[-1]的元素然后把A[n-1]插在該元素的后面。這種算法被稱為直接插入排序(straight insertion sort),或者簡稱為插入排序(insertion sort)。4.2 拓?fù)渑判?.3生成祝賀對(duì)象的算法4.4 減常因子算法以上略有時(shí)間再做筆記4.4.1 折半查找對(duì)于有序數(shù)組的查找來說折半查找是一種性能卓越的算法。它通過比較查找鍵K和數(shù)組中間元素A[m]來完成查找工作。如果它們相等算法結(jié)束。否則如果KA[m],就對(duì)數(shù)組的前半部分執(zhí)行該操作如果KA[m],則對(duì)數(shù)組的后半部分執(zhí)行該操作。4.4.2 假幣問題4.4.3 俄式乘法4.4.4 約瑟夫斯問題 三問題略4.5減可變規(guī)模算法4.5.1 插值查找有時(shí)間再做筆記第五章 分治法基本思想將一個(gè)規(guī)模為n的問題分解為k個(gè)規(guī)模較小的子問題這些子問題互相獨(dú)立且原問題相同。遞歸地解這些子問題然后將各子問題的解合并得到原問題的解。精髓分——將問題分解為規(guī)模更小的子問題。治——將這些規(guī)模更小的子問題逐個(gè)擊破。合——將已解決的子問題合并最終得到原問題的解。5.1 合并排序圖5.2演示的是用合并排序算法對(duì)數(shù)列8,3,2,9,7,1,5,4進(jìn)行排序的操作過程。5.2 快速排序如何系統(tǒng)學(xué)習(xí)網(wǎng)絡(luò)安全/黑客網(wǎng)絡(luò)安全不是「速成黑客」而是守護(hù)數(shù)字世界的騎士修行。當(dāng)你第一次用自己寫的腳本檢測出漏洞時(shí)那種創(chuàng)造的快樂遠(yuǎn)勝于電影里的炫技。裝上虛擬機(jī)從配置第一個(gè)Linux環(huán)境開始腳踏實(shí)地從基礎(chǔ)命令學(xué)起相信你一定能成為一名合格的黑客。如果你還不知道從何開始我自己整理的282G的網(wǎng)絡(luò)安全教程可以分享我也是一路自學(xué)走過來的很清楚小白前期學(xué)習(xí)的痛楚你要是沒有方向還沒有好的資源根本學(xué)不到東西下面是我整理的網(wǎng)安資源希望能幫到你。需要的話可以V掃描下方二維碼聯(lián)系領(lǐng)取~如果二維碼失效可以點(diǎn)擊下方鏈接去拿一樣的哦【CSDN大禮包】最新網(wǎng)絡(luò)安全/網(wǎng)安技術(shù)資料包~282G無償分享1.從0到進(jìn)階主流攻防技術(shù)視頻教程包含紅藍(lán)對(duì)抗、CTF、HW等技術(shù)點(diǎn)2.入門必看攻防技術(shù)書籍pdf書面上的技術(shù)書籍確實(shí)太多了這些是我精選出來的還有很多不在圖里3.安裝包/源碼主要攻防會(huì)涉及到的工具安裝包和項(xiàng)目源碼防止你看到這連基礎(chǔ)的工具都還沒有4.面試試題/經(jīng)驗(yàn)網(wǎng)絡(luò)安全崗位面試經(jīng)驗(yàn)總結(jié)誰學(xué)技術(shù)不是為了賺$呢找個(gè)好的崗位很重要需要的話可以V掃描下方二維碼聯(lián)系領(lǐng)取~因篇幅有限資料較為敏感僅展示部分資料添加上方即可獲取如果二維碼失效可以點(diǎn)擊下方鏈接去拿一樣的哦【CSDN大禮包】最新網(wǎng)絡(luò)安全/網(wǎng)安技術(shù)資料包~282G無償分享