數(shù)據(jù)結(jié)構(gòu)

1 說(shuō)說(shuō)一個(gè)算法有哪些時(shí)間復(fù)雜度？歸并算法時(shí)間復(fù)雜度是多少？?????

一個(gè)算法的時(shí)間復(fù)雜度通常包括以下常見(jiàn)類(lèi)型及對(duì)應(yīng)典型算法示例?：

?O(1)?

• 常數(shù)時(shí)間復(fù)雜度
• 示例：數(shù)組隨機(jī)訪問(wèn)、絕對(duì)值計(jì)算（如 abs(x)）

?O(n)?

• 線性時(shí)間復(fù)雜度
• 示例：線性查找、計(jì)數(shù)排序、基數(shù)排序

?O(n2)?

• 平方時(shí)間復(fù)雜度
• 示例：冒泡排序、插入排序、選擇排序

?O(logn)?

• 對(duì)數(shù)時(shí)間復(fù)雜度
• 示例：二分查找、最大公約數(shù)計(jì)算（如 __gcd(a,b)）

?O(n logn)?

• 線性對(duì)數(shù)時(shí)間復(fù)雜度
• 示例：快速排序（平均情況）、歸并排序、堆排序

?O(2?)?

• 指數(shù)時(shí)間復(fù)雜度
• 示例：窮舉法解決子集問(wèn)題

?歸并排序的時(shí)間復(fù)雜度?為 ?O(n logn)?，具體分析如下?：

• 分治策略?：歸并排序?qū)?shù)組遞歸拆分為兩半，拆分次數(shù)為 log?n 層。
• ?合并操作?：每層合并需要 O(n) 時(shí)間遍歷所有元素。
• ?總復(fù)雜度?：O(n) × O(logn) = O(n logn)。

其時(shí)間復(fù)雜度在所有情況下（最好/平均/最壞）均保持穩(wěn)定，是高效且穩(wěn)定的排序算法。

2 說(shuō)說(shuō)數(shù)組時(shí)間復(fù)雜度，什么場(chǎng)景下使用？???

一、數(shù)組的時(shí)間復(fù)雜度分析

數(shù)組作為線性數(shù)據(jù)結(jié)構(gòu)，其時(shí)間復(fù)雜度主要取決于操作類(lèi)型：

?隨機(jī)訪問(wèn)?：通過(guò)下標(biāo)直接訪問(wèn)元素，時(shí)間復(fù)雜度為 ?O(1)?（如 array[i]）?。

?插入/刪除?：

• 在數(shù)組末尾操作，時(shí)間復(fù)雜度為 ?O(1)?（如動(dòng)態(tài)擴(kuò)容前的追加操作）?。
• 在中間或開(kāi)頭操作，需移動(dòng)后續(xù)元素，時(shí)間復(fù)雜度為 ?O(n)?（如插入到第k個(gè)位置）?。

?遍歷操作?：遍歷所有元素的時(shí)間復(fù)雜度為 ?O(n)??。

二、數(shù)組的適用場(chǎng)景

數(shù)組因其內(nèi)存連續(xù)、訪問(wèn)高效的特點(diǎn)，適用于以下場(chǎng)景：

?存儲(chǔ)固定大小的數(shù)據(jù)集合?

• 如存儲(chǔ)學(xué)生成績(jī)、用戶信息等已知數(shù)量的同類(lèi)型數(shù)據(jù)?。
• 示例：Java中靜態(tài)初始化 int[] scores = {90, 85, 78};?。

?需要高頻隨機(jī)訪問(wèn)的場(chǎng)景?

• 如算法中的二分查找、快速排序等依賴(lài)下標(biāo)快速定位的場(chǎng)景?。
• 示例：Arrays.binarySearch() 實(shí)現(xiàn)依賴(lài)于數(shù)組的隨機(jī)訪問(wèn)特性?。

?多維數(shù)據(jù)表示?

• 如矩陣運(yùn)算、圖像像素存儲(chǔ)等需要多維結(jié)構(gòu)的場(chǎng)景?。
• 示例：二維數(shù)組表示棋盤(pán) int[][] chessBoard = new int;?。

?緩存優(yōu)化與性能敏感場(chǎng)景?

• 內(nèi)存連續(xù)特性可提高CPU緩存命中率，適用于底層開(kāi)發(fā)（如網(wǎng)絡(luò)框架）?。

?批量數(shù)據(jù)操作?

• 如遍歷統(tǒng)計(jì)、批量修改等需要順序訪問(wèn)的場(chǎng)景（如計(jì)算平均分）?。

三、總結(jié)

數(shù)組在?隨機(jī)訪問(wèn)性能強(qiáng)、數(shù)據(jù)規(guī)模固定、內(nèi)存連續(xù)?的場(chǎng)景下表現(xiàn)優(yōu)異，但插入/刪除效率低且擴(kuò)容成本高?。實(shí)際開(kāi)發(fā)中需根據(jù)需求權(quán)衡其優(yōu)缺點(diǎn)，例如在需要?jiǎng)討B(tài)擴(kuò)容時(shí)，可結(jié)合鏈表或 ArrayList 使用。

3 說(shuō)說(shuō)vector的實(shí)現(xiàn)原理????

vector 是 C++ 標(biāo)準(zhǔn)模板庫(kù)（STL）中的一個(gè)容器，它實(shí)現(xiàn)了動(dòng)態(tài)數(shù)組的功能。以下是 vector 的實(shí)現(xiàn)原理的詳細(xì)介紹：

數(shù)據(jù)存儲(chǔ)

• vector 內(nèi)部使用一塊連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)元素。這就像在內(nèi)存中開(kāi)辟了一段連續(xù)的 “線性空間”，元素按照順序依次存放，這種連續(xù)存儲(chǔ)的方式使得 vector 可以像數(shù)組一樣通過(guò)下標(biāo)快速訪問(wèn)元素，時(shí)間復(fù)雜度為 O (1)。

動(dòng)態(tài)增長(zhǎng)機(jī)制

• vector 能夠根據(jù)需要?jiǎng)討B(tài)地調(diào)整自身的大小。當(dāng)向 vector 中插入元素時(shí)，如果當(dāng)前的內(nèi)存空間已滿，vector 會(huì)自動(dòng)分配一塊更大的內(nèi)存空間，通常是當(dāng)前容量的兩倍，然后將原來(lái)的元素復(fù)制到新的內(nèi)存空間中，最后釋放原來(lái)的內(nèi)存空間。
• 以一個(gè)初始容量為 5 的 vector 為例，當(dāng)插入第 6 個(gè)元素時(shí)，vector 會(huì)分配一塊容量為 10 的新內(nèi)存空間，將前 5 個(gè)元素復(fù)制到新空間，再插入第 6 個(gè)元素，然后釋放原來(lái)容量為 5 的內(nèi)存空間。

迭代器

• vector 提供了迭代器來(lái)訪問(wèn)和遍歷容器中的元素。迭代器在 vector 中的工作原理類(lèi)似于指針，它可以指向 vector 中的某個(gè)元素，通過(guò)迭代器的移動(dòng)操作，可以順序訪問(wèn) vector 中的每個(gè)元素。
• 可以使用 begin () 函數(shù)獲取指向 vector 第一個(gè)元素的迭代器，使用 end () 函數(shù)獲取指向 vector 最后一個(gè)元素的下一個(gè)位置的迭代器。

元素插入和刪除

• 插入操作：當(dāng)在 vector 的任意位置插入元素時(shí)，需要將插入位置之后的元素依次向后移動(dòng)，為新元素騰出空間，然后將新元素插入到指定位置。如果插入位置是 vector 的末尾，直接將元素插入到末尾即可，時(shí)間復(fù)雜度通常為 O (1)；但如果是在 vector 的開(kāi)頭或中間插入元素，時(shí)間復(fù)雜度為 O (n)，n 為 vector 中元素的個(gè)數(shù)。
• 刪除操作：刪除 vector 中的元素時(shí)，需要將刪除位置之后的元素依次向前移動(dòng)，填補(bǔ)被刪除元素的位置，以保持內(nèi)存的連續(xù)性。同樣，如果刪除的是 vector 的末尾元素，時(shí)間復(fù)雜度為 O (1)；如果刪除的是開(kāi)頭或中間的元素，時(shí)間復(fù)雜度為 O (n)。

內(nèi)存管理

• vector 負(fù)責(zé)管理自己的內(nèi)存空間，在創(chuàng)建 vector 對(duì)象時(shí)，會(huì)根據(jù)初始容量分配一定大小的內(nèi)存空間。當(dāng) vector 對(duì)象被銷(xiāo)毀時(shí)，會(huì)自動(dòng)釋放其所占用的內(nèi)存空間，防止內(nèi)存泄漏。
• 在 vector 的大小發(fā)生變化時(shí)，它會(huì)合理地申請(qǐng)和釋放內(nèi)存，以確保在滿足存儲(chǔ)需求的同時(shí)，盡可能地提高內(nèi)存的使用效率。

4 總結(jié)一下數(shù)組與鏈表的區(qū)別????

• 存儲(chǔ)結(jié)構(gòu)：數(shù)組是連續(xù)存儲(chǔ)，鏈表是節(jié)點(diǎn)式的非連續(xù)存儲(chǔ)。
• 訪問(wèn)方式：數(shù)組可通過(guò)下標(biāo)隨機(jī)訪問(wèn)，時(shí)間復(fù)雜度為 O (1)；鏈表需順序訪問(wèn)，時(shí)間復(fù)雜度為 O (n)。
• 插入刪除操作：數(shù)組在中間或頭部插入刪除需移動(dòng)大量元素，時(shí)間復(fù)雜度為 O (n)；鏈表只需修改指針，時(shí)間復(fù)雜度一般為 O (1)。
• 內(nèi)存分配：數(shù)組靜態(tài)分配內(nèi)存，大小固定；鏈表動(dòng)態(tài)分配內(nèi)存，大小可靈活變化。

5 棧和隊(duì)列的區(qū)別????

棧和隊(duì)列的區(qū)別主要體現(xiàn)在：

• 數(shù)據(jù)進(jìn)出原則：棧遵循后進(jìn)先出（LIFO）原則，如同彈夾，最后壓入的子彈最先彈出；隊(duì)列遵循先進(jìn)先出（FIFO）原則，類(lèi)似排隊(duì)，先到的先處理。
• 操作方式：棧的插入和刪除操作都在棧頂進(jìn)行；隊(duì)列的插入在隊(duì)尾，刪除在隊(duì)頭。
• 應(yīng)用場(chǎng)景：棧常用于函數(shù)調(diào)用、表達(dá)式求值等；隊(duì)列常用于任務(wù)調(diào)度、緩存管理等。

6 說(shuō)說(shuō)二叉堆???

二叉堆是一種基于完全二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，常用于實(shí)現(xiàn)優(yōu)先隊(duì)列。以下是關(guān)于二叉堆的詳細(xì)說(shuō)明：

一、核心概念

1. 定義完全二叉樹(shù)：除最后一層外，其他層節(jié)點(diǎn)填滿，且最后一層節(jié)點(diǎn)從左到右排列。堆性質(zhì)：最大堆：每個(gè)節(jié)點(diǎn)的值 ≥ 其子節(jié)點(diǎn)的值。最小堆：每個(gè)節(jié)點(diǎn)的值 ≤ 其子節(jié)點(diǎn)的值。
2. 存儲(chǔ)方式使用數(shù)組存儲(chǔ)，無(wú)需額外指針。節(jié)點(diǎn) i 的子節(jié)點(diǎn)為 2i+1（左）和 2i+2（右），父節(jié)點(diǎn)為 (i-1)/2。

二、關(guān)鍵操作

1. 插入（以最小堆為例）將元素添加到數(shù)組末尾。向上調(diào)整（Shift Up）：若新元素小于父節(jié)點(diǎn)，與父節(jié)點(diǎn)交換，重復(fù)直到滿足堆性質(zhì)。
2. 刪除（以最小堆為例）刪除根節(jié)點(diǎn)（最小值）。用最后一個(gè)元素填補(bǔ)根節(jié)點(diǎn)位置。向下調(diào)整（Shift Down）：若當(dāng)前節(jié)點(diǎn)大于子節(jié)點(diǎn)，與較小子節(jié)點(diǎn)交換，重復(fù)直到滿足堆性質(zhì)。
3. 堆化（Heapify）將普通數(shù)組轉(zhuǎn)換為堆結(jié)構(gòu)。從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始，逐個(gè)節(jié)點(diǎn)向下調(diào)整。

三、應(yīng)用場(chǎng)景

1. 優(yōu)先隊(duì)列：快速獲取最大 / 最小值。
2. 堆排序：通過(guò)堆結(jié)構(gòu)實(shí)現(xiàn)高效排序。
3. 圖算法：如 Dijkstra 算法（求最短路徑）。
4. 找第 K 大 / 小元素：用堆優(yōu)化時(shí)間復(fù)雜度。

7 說(shuō)說(shuō)哈希表???

哈希表（Hash Table）是一種通過(guò)哈希函數(shù)實(shí)現(xiàn)快速查找、插入和刪除的數(shù)據(jù)結(jié)構(gòu)，其核心思想是將鍵映射到存儲(chǔ)位置。以下是關(guān)于哈希表的詳細(xì)說(shuō)明：

一、核心概念

1. 定義哈希表由 鍵值對(duì)（Key-Value