演算法基本觀念收藏(2021/06/29)
演算法基本觀念收藏(2021/06/29)
資料來源: https://mp.weixin.qq.com/s/_lHkzk1D235BQrDVkiGTtw
1.數組(陣列)和鍊錶(List)的區別
數組是將元素在內存中連續存放，由於每個元素佔用內存相同，可以通過基底位置和位移迅速訪問數組中任何元素。
鍊錶是一種上一個元素的引用指向下一個元素的存儲結構，鍊錶通過指針來連接元素與元素；
數組是連續存儲的，鍊錶是散列存儲的。數組隨機訪問性強（通過基底位置和位移進行快速定位），所以數組的查詢比鍊錶要快，鍊錶不能隨機查找，必須從第一個開始遍歷，查找效率低。
數組插入和刪除效率低（插入和刪除需要移動數據），鍊錶插入刪除速度快（因為有next指針指向其下一個節點，通過改變指針的指向可以方便的增加刪除元素）
2.堆,棧,堆棧,隊列
堆(heap)：堆是一種經過排序的樹形數據結構，每個結點都有一個值。堆通常是一個可以被看做一棵樹的數組對象。堆總是滿足下列性質：堆中某個節點的值總是不大於或不小於其父節點的值,堆總是一棵完全二叉樹。
棧(stack): 它是一種具有後進先出性質的數據結構，也就是說後存放的先取，先存放的後取。
堆棧本身就是棧.
隊列是先進先出，有出口和入口。
3.堆和棧的區別：
①堆棧空間分配區別：1）、棧（操作系統）：由操作系統自動分配釋放，存放函數的參數值，局部變量的值等。其操作方式類似於數據結構中的棧；2）、堆（操作系統）：一般由程序員分配釋放， 若程序員不釋放，程序結束時可能由OS回收，分配方式倒是類似於鍊錶。
②堆棧緩存方式區別：1）、棧使用的是一級緩存，他們通常都是被調用時處於存儲空間中，調用完畢立即釋放；2）、堆是存放在二級緩存中，生命週期由虛擬機的垃圾回收算法來決定（並不是一旦成為孤兒對象就能被回收）。所以調用這些對象的速度要相對來得低一些。
堆：內存中，存儲的是引用數據類型，引用數據類型無法確定大小，堆實際上是一個在內存中使用到內存中零散空間的鍊錶結構的存儲空間，堆的大小由引用類型的大小直接決定，引用類型的大小的變化直接影響到堆的變化
棧：是內存中存儲值類型的，大小為2M，超出則會報錯，內存溢出
③堆棧數據結構區別：堆（數據結構）：堆可以被看成是一棵樹，如：堆排序；棧（數據結構）：一種先進後出的數據結構。特點：先進後出
4.堆和棧的訪問哪個更快
棧是編譯時分配空間，而堆是動態分配（運行時分配空間），所以棧的速度快。
5.快排和堆排
快速排序：最常用的排序算法，速度通常也是最快的。時間複雜度：O（nlogn）
最壞：O（n^2） 空間複雜度：O（nlgn） 不穩定（比如5 3 3 4 3 8 9 10 11 這個序列，在中樞元素5和3交換就會把元素3的穩定性打亂）
實現原理：快排主要是通過選擇一個關鍵值作為基準值。比基準值小的都在左邊序列（一般是無序的），比基準值大的都在右邊（一般是無序的）。依此遞歸，達到總體待排序序列都有序。
堆排序：堆排序是指利用堆這種數據結構進行設計的一種排序算法。堆排序利用了大根堆(或小根堆)堆頂記錄的關鍵字最大(或最小)這一特徵，使得在當前無序區中選取最大(或最小)關鍵字的記錄變得簡單。
時間複雜度：O（n*logn）特別適用於數據量很大的場合（百萬級數據）。因為快排和歸併排序都是基於遞歸的，數據量很大的情況下容易發生堆棧溢出。排序速度略低於快排。也是一種不穩定的排序算法。
6.介紹快排，描述一下最壞的情況
時間複雜度：最好情況O(nlogn)——Partition函數每次恰好能均分序列，其遞歸樹的深度就為.log2n.+1（.x.表示不大於x的最大整數），即僅需遞歸log2n次；最壞情況O（n^2）,每次劃分只能將序列分為一個元素與其他元素兩部分，這時的快速排序退化為冒泡排序，如果用數畫出來，得到的將會是一棵單斜樹，也就是說所有所有的節點只有左（右）節點的樹；平均時間複雜度O(nlogn)。
解釋一下快排的思路，時間複雜度，穩定嗎？（略，不穩定） 穩定的排序都有哪些？（插，歸併，冒泡） 解釋一下堆排序？（不斷得維護一個最大/小堆，時間複雜度nlgn）
7.快排和堆排的優缺點和應用場景
a : 時間複雜度都是o(nlogn)
b : 效率: 快排>歸併>堆排
c : 三種算法的優缺點:快排: 極端情況下排序效率很低
歸併:需要額外的內存開銷，堆排序: 在快的排序算法中,相對較慢, 但應用很廣.
8.知道哪些排序算法排序的空間複雜度各種排序算法的原理
冒泡排序、簡單選擇、直接插入、快速排序、堆排序、希爾排序、歸併排序、基數排序。
冒泡排序：每當相鄰的兩個數比較後發現它們的排序與排序要求相反時，就將它們互換。
快速排序：選擇一個基準元素，通常選擇第一個元素或者最後一個元素，通過一趟掃描，將待排序的元素分成兩部分，一部分比基準元素小，一部分大於等於基準元素，此時基準元素在其排好序後的正確位置，然後再用同樣的方法遞歸地排序劃分的兩部分。
簡單選擇排序：在要排序的一組數中，選出最小的一個數與第一個位置的數交換；然後在剩下的數當中再找最小的與第二個位置的數交換，如此循環到倒數第二個數和最後一個數為止。
堆排序：堆排序是一種樹形選擇排序，是對直接排序的有效改進。
直接插入排序：在要排序的一組數中，假設前面（n-1）[n>=2]個數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這n個數也是排好順序的。如此反复循環，直到全部排好順序。
希爾排序：先將要排序的一組數按某個增量d（n/2,n為要排序數的個數）分成若干組，每組記錄的下標相差d，對每組中全部元素進行直接插入排序，然後再用一個較小的增量(d/2)對它進行分組，在每組中再進行直接插入排序。當增量減至1時，進行直接插入排序後，排序完成。
歸併排序：歸併（Merge）排序法是將兩個（或兩個以上）有序表合併成一個新的有序表，即把帶排序序列分為若干個子序列，每個子序列是有序的。然後再把有序子序列合併為整體有序序列。
基數排序：將所有待比較數值（正整數）統一為同樣的數位長度，數位較短的數前面補零。然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後，數列就變成一個有序序列。
9.二叉樹、平衡二叉樹、完全二叉樹、滿二叉樹
二叉樹的概念：一棵二叉樹是節點的一個有限集合，該集合或者為空，或者由一個根節點加上兩棵左子樹和右子樹組成。
平衡二叉樹，又稱AVL樹。它或者是一棵空樹，或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的高度之差之差的絕對值不超過1 。
滿二叉樹：一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。
完全二叉樹：葉子節點只能分佈在樹的倒數第1層和倒數第二層，倒數第二層的節點必須是滿的，倒數第一層的節點可以不全是滿的，但是所有的節點都只能集中在樹的左側。這也說明，倒數第二層的節點肯定不會出現只有右子樹，沒有左子樹的情況。在構建完全二叉樹時，插入節點一定先插入左子樹，再插入右子樹。
10.為什麼要構造成二叉樹，N叉樹可不可以
二叉樹是按值來保存元素，也按值來訪問元素。
11.紅黑樹
紅黑樹是一種自平衡樹，它也是一顆二叉樹。既然能保持平衡，說明它和AVL 樹類似，在插入或者刪除時肯定有調整的過程，只不過這個調整過程並不像AVL 樹那樣繁瑣。為何紅黑樹使用得比AVL 樹更多，就是因為紅黑樹它的調整過程迅速且簡介。
紅黑樹有以下五個特性：
性質1：節點是紅色或黑色
性質2：根是黑色
性質3：所有葉子都是黑色。葉子是NIL 節點，也就是Null 節點
性質4：如果一個節點是紅的，則它的兩個兒子都是黑的
性質5：從任一節點到其葉子的所有簡單路徑都包含相同數目的黑色節點。
12.遞歸有什麼缺點 A:當遞歸層數很多的時候，容易造成內存溢出
13.遇到哈希(Hash)衝突怎麼辦
①開放定址法：為產生衝突的地址求得一個地址序列(),其中。其中m為表的長度,而增量有三種取值方法,線性探測再散列,平方探測再散列,隨即探測再散列。
②鏈地址法：將所有Hash地址相同的記錄都鏈接在同一鍊錶中，再Hash法，同時構造多個不同的Hash函數,當產生衝突時,計算另一個Hash函數地址直到不再發生衝突為止。
③建立公共溢出區：將Hash表分為基本表和溢出表,若是與基本表發生衝突,都放入溢出表。
14.跳表
跳表是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鍊錶，跳表在原有的有序鍊錶上面增加了多級索引，通過索引來實現快速查找，跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。
15.動態規劃和分治的區別與聯繫，各自適應哪些情況
動態規劃：通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。動態規劃常常適用於有重疊子問題和最優子結構性質的問題。
分治法的基本思想：
將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
共同點：二者都要求原問題具有最優子結構性質,都是將原問題分而治之,分解成若干個規模較小(小到很容易解決的程序)的子問題.然後將子問題的解合併,形成原問題的解.
不同點：分治法將分解後的子問題看成相互獨立的，通過用遞歸來做。
動態規劃將分解後的子問題理解為相互間有聯繫,有重疊部分，需要記憶，通常用迭代來做。
16.圖的遍歷方式
從圖中某一頂點出發訪遍圖中其餘頂點，且使每一個頂點僅被訪問一次，這一過程就叫做圖的遍歷。根據遍歷路徑的不同，通常有兩種遍歷圖的方法：深度優先遍歷和廣度優先遍歷。它們對無向圖和有向圖都適用。圖的遍曆算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。