最近在準(zhǔn)備悉尼大學(xué)COMP2123課程的第一周內(nèi)容發(fā)現(xiàn)很多同學(xué)對(duì)數(shù)據(jù)結(jié)構(gòu)與算法的入門概念感到抽象特別是如何將理論應(yīng)用到實(shí)際代碼中。本文將結(jié)合Week1公開課的核心知識(shí)點(diǎn)系統(tǒng)梳理從環(huán)境搭建到基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)的完整流程并附上可運(yùn)行的代碼示例和常見誤區(qū)分析。無論你是剛開始學(xué)習(xí)這門課還是希望鞏固算法基礎(chǔ)都能從中獲得清晰的實(shí)踐路徑。1. 數(shù)據(jù)結(jié)構(gòu)與算法入門為什么它們?nèi)绱酥匾陂_始敲代碼之前我們首先要理解學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法的根本目的。簡(jiǎn)單來說數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織、管理和存儲(chǔ)格式其目的是為了高效地訪問和修改數(shù)據(jù)。算法則是解決特定問題的一系列清晰指令。兩者相輔相成高效的數(shù)據(jù)結(jié)構(gòu)是設(shè)計(jì)高效算法的基礎(chǔ)。1.1 從生活場(chǎng)景理解核心概念想象一下你去圖書館找一本書。如果書籍雜亂無章地堆在地上糟糕的數(shù)據(jù)結(jié)構(gòu)你可能需要花費(fèi)數(shù)小時(shí)低效的算法一本本翻找。如果書籍按照杜威十進(jìn)制分類法整齊排列在書架上良好的數(shù)據(jù)結(jié)構(gòu)你就可以根據(jù)索書號(hào)快速定位到大致區(qū)域高效的搜索算法從而在幾分鐘內(nèi)找到目標(biāo)。在計(jì)算機(jī)科學(xué)中常見的“找書”問題包括搜索在一組數(shù)據(jù)中查找特定項(xiàng)。排序?qū)⒁唤M數(shù)據(jù)按特定順序排列。插入/刪除在數(shù)據(jù)集合中添加或移除一項(xiàng)。選擇不同的數(shù)據(jù)結(jié)構(gòu)如數(shù)組、鏈表、樹和算法如線性搜索、二分搜索、快速排序解決這些問題的效率會(huì)有天壤之別。這就是我們學(xué)習(xí)這門課的意義為特定問題選擇最合適的“工具”從而編寫出運(yùn)行更快、占用資源更少的程序。1.2 算法復(fù)雜度分析衡量效率的標(biāo)尺我們?nèi)绾瘟炕粋€(gè)算法的“好壞”這就需要引入算法復(fù)雜度分析主要關(guān)注時(shí)間復(fù)雜度和空間復(fù)雜度。時(shí)間復(fù)雜度指算法執(zhí)行所需的時(shí)間隨輸入數(shù)據(jù)規(guī)模通常用n表示的增長(zhǎng)趨勢(shì)。我們使用大O符號(hào)Big O notation來描述。空間復(fù)雜度指算法執(zhí)行過程中所需的最大內(nèi)存空間同樣用大O符號(hào)描述。以下是幾種常見的時(shí)間復(fù)雜度從上到下效率依次降低O(1)常數(shù)時(shí)間。操作時(shí)間與輸入規(guī)模無關(guān)。例如訪問數(shù)組中的一個(gè)元素。O(log n)對(duì)數(shù)時(shí)間。效率非常高典型例子是二分查找。O(n)線性時(shí)間。操作時(shí)間與輸入規(guī)模成正比。例如遍歷一個(gè)數(shù)組。O(n log n)線性對(duì)數(shù)時(shí)間。許多高效排序算法如歸并排序、快速排序的平均復(fù)雜度。O(n2)平方時(shí)間。通常出現(xiàn)在嵌套循環(huán)中如簡(jiǎn)單的冒泡排序。O(2^n)指數(shù)時(shí)間。效率極低通常意味著算法設(shè)計(jì)有嚴(yán)重問題如求解所有子集。在Week1中理解大O表示法并能夠初步分析簡(jiǎn)單程序的時(shí)間復(fù)雜度是首要目標(biāo)。2. 環(huán)境準(zhǔn)備與工具選擇工欲善其事必先利其器。一個(gè)合適的開發(fā)環(huán)境能讓你更專注于邏輯本身而非環(huán)境配置問題。2.1 編程語(yǔ)言選擇COMP2123課程通常不強(qiáng)制限定編程語(yǔ)言但教學(xué)示例和作業(yè)可能以Java、Python或C為主。選擇的原則是課程推薦優(yōu)先使用課程提供的示例代碼語(yǔ)言。個(gè)人熟練度選擇你最能清晰表達(dá)算法的語(yǔ)言。算法表現(xiàn)力Python語(yǔ)法簡(jiǎn)潔適合快速實(shí)現(xiàn)原型Java/C在強(qiáng)調(diào)內(nèi)存管理和性能細(xì)節(jié)時(shí)更佳。本文后續(xù)示例將主要使用Python因其語(yǔ)法接近偽代碼易于理解。對(duì)于關(guān)鍵概念也會(huì)提供Java版本的對(duì)比。2.2 開發(fā)環(huán)境搭建對(duì)于Python安裝Python訪問 python.org 下載最新穩(wěn)定版如3.11。安裝時(shí)務(wù)必勾選“Add Python to PATH”。驗(yàn)證安裝打開終端Windows CMD/PowerShell, macOS/Linux Terminal輸入python --version查看版本。選擇編輯器初學(xué)者推薦VS Code。輕量、插件豐富安裝Python擴(kuò)展。集成環(huán)境PyCharm Community Edition功能強(qiáng)大免費(fèi)。對(duì)于Java安裝JDK下載并安裝OpenJDK 17或Oracle JDK 17。配置環(huán)境變量設(shè)置JAVA_HOME并將bin目錄加入PATH。驗(yàn)證安裝終端輸入java -version和javac -version。選擇編輯器IntelliJ IDEA Community Edition 或 Eclipse。2.3 第一個(gè)程序從“Hello, World!”到復(fù)雜度分析讓我們從一個(gè)簡(jiǎn)單的例子開始并分析其復(fù)雜度。Python 示例計(jì)算列表和# 文件sum_list.py def sum_list(numbers): 計(jì)算整數(shù)列表的總和。 時(shí)間復(fù)雜度O(n)需要遍歷列表中的n個(gè)元素。 空間復(fù)雜度O(1)只使用了固定數(shù)量的變量total, num。 total 0 for num in numbers: total num return total # 測(cè)試代碼 if __name__ __main__: my_list [1, 2, 3, 4, 5] result sum_list(my_list) print(fThe sum of {my_list} is: {result}) # 輸出 The sum of [1, 2, 3, 4, 5] is: 15Java 示例計(jì)算數(shù)組和// 文件SumArray.java public class SumArray { /** * 計(jì)算整數(shù)數(shù)組的總和。 * 時(shí)間復(fù)雜度O(n) * 空間復(fù)雜度O(1) */ public static int sumArray(int[] numbers) { int total 0; for (int num : numbers) { total num; } return total; } public static void main(String[] args) { int[] myArray {1, 2, 3, 4, 5}; int result sumArray(myArray); System.out.println(The sum of the array is: result); // 輸出 The sum of the array is: 15 } }復(fù)雜度分析兩個(gè)函數(shù)都包含一個(gè)遍歷所有元素的循環(huán)。如果列表/數(shù)組有n個(gè)元素循環(huán)就會(huì)執(zhí)行n次。因此時(shí)間復(fù)雜度是O(n)。我們只使用了固定數(shù)量的額外變量total所以空間復(fù)雜度是O(1)。3. 核心數(shù)據(jù)結(jié)構(gòu)一數(shù)組與動(dòng)態(tài)數(shù)組Week1通常會(huì)從最基礎(chǔ)、最常用的數(shù)據(jù)結(jié)構(gòu)——數(shù)組開始講起。3.1 靜態(tài)數(shù)組固定大小的連續(xù)存儲(chǔ)數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu)在內(nèi)存中占用一塊連續(xù)的空間用于存儲(chǔ)相同類型的元素。每個(gè)元素可以通過索引下標(biāo)直接訪問。特點(diǎn)優(yōu)點(diǎn)隨機(jī)訪問速度快通過索引訪問任意元素的時(shí)間復(fù)雜度為 O(1)。內(nèi)存空間緊湊連續(xù)存儲(chǔ)緩存友好。缺點(diǎn)大小固定創(chuàng)建時(shí)需指定容量無法動(dòng)態(tài)擴(kuò)容。插入/刪除成本高在中間插入或刪除元素需要移動(dòng)后續(xù)所有元素平均時(shí)間復(fù)雜度為 O(n)。Python 列表 vs 數(shù)組Python內(nèi)置的list實(shí)際上是一個(gè)動(dòng)態(tài)數(shù)組而非傳統(tǒng)意義上的靜態(tài)數(shù)組。它封裝了擴(kuò)容等復(fù)雜操作。Java 數(shù)組示例// 聲明并初始化一個(gè)靜態(tài)數(shù)組 int[] staticArray new int[5]; // 容量為5初始值全為0 staticArray[0] 10; // O(1) 訪問 // staticArray[5] 20; // 錯(cuò)誤ArrayIndexOutOfBoundsException索引越界 // 遍歷數(shù)組 for (int i 0; i staticArray.length; i) { System.out.println(staticArray[i]); }3.2 動(dòng)態(tài)數(shù)組可擴(kuò)容的數(shù)組為了解決靜態(tài)數(shù)組大小固定的問題動(dòng)態(tài)數(shù)組如Python的listJava的ArrayListC的std::vector在內(nèi)部實(shí)現(xiàn)上仍然使用一塊連續(xù)內(nèi)存但當(dāng)容量不足時(shí)會(huì)執(zhí)行以下操作分配一塊更大的新內(nèi)存通常是原容量的1.5或2倍。將舊數(shù)組的所有元素復(fù)制到新數(shù)組。釋放舊數(shù)組的內(nèi)存。將新元素插入。這個(gè)擴(kuò)容操作的時(shí)間復(fù)雜度是O(n)但分?jǐn)偟蕉啻尾迦氩僮骱笃渚鶖倳r(shí)間復(fù)雜度仍可視為O(1)。Python 動(dòng)態(tài)數(shù)組列表操作# 創(chuàng)建一個(gè)空列表動(dòng)態(tài)數(shù)組 dynamic_list [] # 初始容量可能很小 # 追加元素 - 平均O(1) dynamic_list.append(1) dynamic_list.append(2) dynamic_list.append(3) print(dynamic_list) # 輸出: [1, 2, 3] # 在指定索引插入元素 - O(n) dynamic_list.insert(1, 99) # 在索引1處插入99 print(dynamic_list) # 輸出: [1, 99, 2, 3] # 刪除指定索引元素 - O(n) popped_value dynamic_list.pop(2) # 刪除并返回索引2的元素 (2) print(fRemoved {popped_value}, list now: {dynamic_list}) # 輸出: Removed 2, list now: [1, 99, 3] # 隨機(jī)訪問 - O(1) print(dynamic_list[0]) # 輸出: 1Java ArrayList 示例import java.util.ArrayList; public class DynamicArrayDemo { public static void main(String[] args) { // 創(chuàng)建一個(gè)ArrayList動(dòng)態(tài)數(shù)組 ArrayListInteger arrayList new ArrayList(); // 添加元素 arrayList.add(10); // O(1) 均攤 arrayList.add(20); arrayList.add(30); System.out.println(arrayList); // 輸出: [10, 20, 30] // 在索引1處插入元素 - O(n) arrayList.add(1, 99); System.out.println(arrayList); // 輸出: [10, 99, 20, 30] // 刪除索引2處的元素 - O(n) arrayList.remove(2); System.out.println(arrayList); // 輸出: [10, 99, 30] // 隨機(jī)訪問 - O(1) System.out.println(arrayList.get(0)); // 輸出: 10 } }4. 核心數(shù)據(jù)結(jié)構(gòu)二鏈表鏈表是另一種基礎(chǔ)的線性數(shù)據(jù)結(jié)構(gòu)它通過“節(jié)點(diǎn)”和“指針”來組織數(shù)據(jù)在內(nèi)存中不必連續(xù)存儲(chǔ)。4.1 鏈表的核心概念節(jié)點(diǎn)鏈表的基本單位包含兩部分data存儲(chǔ)數(shù)據(jù)。next一個(gè)引用或指針指向下一個(gè)節(jié)點(diǎn)。頭節(jié)點(diǎn)指向鏈表第一個(gè)節(jié)點(diǎn)的引用。通過它可以訪問整個(gè)鏈表。尾節(jié)點(diǎn)最后一個(gè)節(jié)點(diǎn)其next指向NonePython或nullJava。4.2 單向鏈表的實(shí)現(xiàn)讓我們用Python和Java分別實(shí)現(xiàn)一個(gè)簡(jiǎn)單的單向鏈表。Python 實(shí)現(xiàn)# 文件singly_linked_list.py class ListNode: 鏈表節(jié)點(diǎn)類 def __init__(self, data0, next_nodeNone): self.data data self.next next_node class SinglyLinkedList: 單向鏈表類 def __init__(self): self.head None # 鏈表頭節(jié)點(diǎn) def append(self, data): 在鏈表末尾添加節(jié)點(diǎn) - O(n) new_node ListNode(data) if not self.head: # 如果鏈表為空 self.head new_node return # 遍歷到鏈表末尾 current self.head while current.next: current current.next current.next new_node def prepend(self, data): 在鏈表頭部添加節(jié)點(diǎn) - O(1) new_node ListNode(data) new_node.next self.head self.head new_node def delete(self, key): 刪除第一個(gè)值為key的節(jié)點(diǎn) - O(n) current self.head # 如果要?jiǎng)h除的是頭節(jié)點(diǎn) if current and current.data key: self.head current.next current None return # 查找要?jiǎng)h除的節(jié)點(diǎn)及其前驅(qū)節(jié)點(diǎn) prev None while current and current.data ! key: prev current current current.next # 如果沒找到 if current is None: return # 執(zhí)行刪除 prev.next current.next current None def search(self, key): 查找值為key的節(jié)點(diǎn) - O(n) current self.head while current: if current.data key: return True current current.next return False def display(self): 打印鏈表 elements [] current self.head while current: elements.append(str(current.data)) current current.next print( - .join(elements) if elements else Empty List) # 測(cè)試代碼 if __name__ __main__: llist SinglyLinkedList() llist.append(1) llist.append(2) llist.append(3) llist.prepend(0) llist.display() # 輸出: 0 - 1 - 2 - 3 print(fSearch 2: {llist.search(2)}) # 輸出: True print(fSearch 5: {llist.search(5)}) # 輸出: False llist.delete(2) llist.display() # 輸出: 0 - 1 - 3Java 實(shí)現(xiàn)// 文件SinglyLinkedList.java class ListNode { int data; ListNode next; ListNode(int data) { this.data data; this.next null; } } public class SinglyLinkedList { private ListNode head; public void append(int data) { ListNode newNode new ListNode(data); if (head null) { head newNode; return; } ListNode current head; while (current.next ! null) { current current.next; } current.next newNode; } public void prepend(int data) { ListNode newNode new ListNode(data); newNode.next head; head newNode; } public void delete(int key) { if (head null) return; if (head.data key) { head head.next; return; } ListNode current head; ListNode prev null; while (current ! null current.data ! key) { prev current; current current.next; } if (current null) return; prev.next current.next; } public boolean search(int key) { ListNode current head; while (current ! null) { if (current.data key) return true; current current.next; } return false; } public void display() { ListNode current head; while (current ! null) { System.out.print(current.data - ); current current.next; } System.out.println(null); } public static void main(String[] args) { SinglyLinkedList list new SinglyLinkedList(); list.append(1); list.append(2); list.append(3); list.prepend(0); list.display(); // 輸出: 0 - 1 - 2 - 3 - null System.out.println(Search 2: list.search(2)); // true System.out.println(Search 5: list.search(5)); // false list.delete(2); list.display(); // 輸出: 0 - 1 - 3 - null } }4.3 鏈表 vs 數(shù)組如何選擇特性數(shù)組 (靜態(tài)/動(dòng)態(tài))鏈表 (單向)內(nèi)存分配連續(xù)內(nèi)存非連續(xù)內(nèi)存 (節(jié)點(diǎn)分散)大小調(diào)整靜態(tài)數(shù)組固定動(dòng)態(tài)數(shù)組可擴(kuò)容但成本高動(dòng)態(tài)按需創(chuàng)建節(jié)點(diǎn)隨機(jī)訪問O(1)通過索引直接訪問O(n)必須從頭遍歷頭部插入/刪除O(n) (需移動(dòng)元素) / O(1) (動(dòng)態(tài)數(shù)組尾部)O(1)中間插入/刪除O(n)O(n) (需先找到位置)空間開銷較小僅存儲(chǔ)數(shù)據(jù)較大每個(gè)節(jié)點(diǎn)需額外存儲(chǔ)指針緩存友好性好 (局部性原理)差選擇指南需要頻繁隨機(jī)訪問元素 →優(yōu)先選擇數(shù)組。需要頻繁在頭部或中間插入/刪除元素且數(shù)據(jù)規(guī)模未知或變化大 →優(yōu)先選擇鏈表。內(nèi)存空間緊張且訪問模式以順序?yàn)橹?→考慮數(shù)組。實(shí)現(xiàn)棧、隊(duì)列等抽象數(shù)據(jù)類型的基礎(chǔ) →兩者皆可視具體操作而定。5. 基礎(chǔ)算法實(shí)踐搜索與排序入門Week1通常會(huì)引入最簡(jiǎn)單的搜索和排序算法讓我們建立對(duì)算法效率的直觀感受。5.1 線性搜索這是最直觀的搜索算法從數(shù)據(jù)結(jié)構(gòu)的一端開始按順序檢查每個(gè)元素直到找到目標(biāo)或遍歷完所有元素。# 文件linear_search.py def linear_search(arr, target): 線性搜索算法。 時(shí)間復(fù)雜度O(n)最壞情況需要檢查所有n個(gè)元素。 空間復(fù)雜度O(1)。 for i, element in enumerate(arr): if element target: return i # 找到返回索引 return -1 # 未找到 # 測(cè)試 my_array [64, 34, 25, 12, 22, 11, 90] target 22 result linear_search(my_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 輸出: Target 22 found at index: 45.2 二分搜索針對(duì)已排序數(shù)組二分搜索是一種效率極高的算法但前提是數(shù)組必須是有序的。它采用分治策略每次比較都將搜索范圍縮小一半。算法步驟設(shè)定搜索范圍的左右邊界left0,rightn-1。當(dāng)left right時(shí) a. 計(jì)算中間索引mid (left right) // 2。 b. 如果arr[mid] target返回mid。 c. 如果arr[mid] target說明目標(biāo)在右側(cè)調(diào)整left mid 1。 d. 如果arr[mid] target說明目標(biāo)在左側(cè)調(diào)整right mid - 1。循環(huán)結(jié)束未找到返回 -1。# 文件binary_search.py def binary_search(arr, target): 二分搜索算法 (迭代版本)。 時(shí)間復(fù)雜度O(log n) 空間復(fù)雜度O(1) left, right 0, len(arr) - 1 while left right: mid (left right) // 2 if arr[mid] target: return mid elif arr[mid] target: left mid 1 # 目標(biāo)在右半部分 else: right mid - 1 # 目標(biāo)在左半部分 return -1 # 測(cè)試 (數(shù)組必須已排序) sorted_array [11, 12, 22, 25, 34, 64, 90] target 22 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 輸出: Target 22 found at index: 2 target 100 result binary_search(sorted_array, target) print(fTarget {target} found at index: {result} if result ! -1 else fTarget {target} not found.) # 輸出: Target 100 not found.5.3 冒泡排序這是最簡(jiǎn)單的排序算法之一通過反復(fù)交換相鄰的無序元素來工作。# 文件bubble_sort.py def bubble_sort(arr): 冒泡排序算法。 時(shí)間復(fù)雜度O(n2) (最壞和平均情況) 空間復(fù)雜度O(1) (原地排序) n len(arr) # 遍歷所有數(shù)組元素 for i in range(n): # 最后 i 個(gè)元素已經(jīng)排好序 swapped False # 優(yōu)化如果一輪沒有交換說明已有序 for j in range(0, n - i - 1): # 如果當(dāng)前元素大于下一個(gè)元素則交換 if arr[j] arr[j 1]: arr[j], arr[j 1] arr[j 1], arr[j] swapped True # 如果內(nèi)層循環(huán)沒有交換任何元素則數(shù)組已排序完成 if not swapped: break return arr # 測(cè)試 unsorted_array [64, 34, 25, 12, 22, 11, 90] sorted_array bubble_sort(unsorted_array.copy()) # 使用副本不改變?cè)瓟?shù)組 print(fOriginal array: {unsorted_array}) print(fSorted array: {sorted_array}) # 輸出: # Original array: [64, 34, 25, 12, 22, 11, 90] # Sorted array: [11, 12, 22, 25, 34, 64, 90]6. 常見問題與調(diào)試技巧學(xué)習(xí)初期理解和調(diào)試代碼中的錯(cuò)誤是至關(guān)重要的技能。6.1 數(shù)組/鏈表操作中的常見錯(cuò)誤索引越界現(xiàn)象IndexError: list index out of range(Python),ArrayIndexOutOfBoundsException(Java)。原因訪問了不存在的索引如arr[len(arr)]。解決始終確保索引在0到len(arr)-1的范圍內(nèi)。在循環(huán)中使用for i in range(len(arr)):或for element in arr:。空指針/引用異?，F(xiàn)象AttributeError: NoneType object has no attribute next(Python),NullPointerException(Java)。原因在鏈表操作中試圖訪問None或null節(jié)點(diǎn)的屬性如current.next而current本身是None/null。解決在訪問節(jié)點(diǎn)屬性前始終檢查節(jié)點(diǎn)是否為None/null。# 正確的鏈表遍歷 current self.head while current is not None: # 或 while current: print(current.data) current current.next無限循環(huán)現(xiàn)象程序卡住不停止。原因鏈表操作中next指針未正確更新導(dǎo)致形成環(huán)或循環(huán)終止條件永遠(yuǎn)無法滿足。解決在紙上畫出鏈表操作步驟仔細(xì)檢查指針的更新邏輯。使用調(diào)試器或打印語(yǔ)句跟蹤變量狀態(tài)。6.2 算法邏輯錯(cuò)誤二分搜索中的整數(shù)溢出問題在計(jì)算中間索引時(shí)mid (left right) // 2在left和right都非常大時(shí)可能導(dǎo)致整數(shù)溢出在C/Java中。解決使用更安全的寫法mid left (right - left) // 2。排序算法不穩(wěn)定性問題冒泡排序是穩(wěn)定的相等元素的相對(duì)順序不變但如果你錯(cuò)誤地使用了進(jìn)行比較可能會(huì)破壞穩(wěn)定性。注意初學(xué)階段理解穩(wěn)定性的概念比實(shí)現(xiàn)它更重要。6.3 調(diào)試建議使用打印語(yǔ)句在關(guān)鍵步驟打印變量值如索引、節(jié)點(diǎn)數(shù)據(jù)、循環(huán)計(jì)數(shù)器。使用IDE調(diào)試器學(xué)習(xí)設(shè)置斷點(diǎn)、單步執(zhí)行、查看變量值。這是最強(qiáng)大的調(diào)試工具。小規(guī)模測(cè)試先用只有2-3個(gè)元素的數(shù)組/鏈表測(cè)試你的代碼確保邊界條件空、只有一個(gè)元素正確處理。編寫測(cè)試用例系統(tǒng)性地測(cè)試你的函數(shù)包括正常情況、邊界情況和異常情況。7. 最佳實(shí)踐與學(xué)習(xí)路線建議掌握基礎(chǔ)知識(shí)后如何高效地繼續(xù)學(xué)習(xí)并應(yīng)用于實(shí)踐7.1 代碼實(shí)現(xiàn)最佳實(shí)踐清晰的命名變量名使用snake_case(Python) 或camelCase(Java)函數(shù)名使用動(dòng)詞開頭類名使用PascalCase。避免使用a,b,x等無意義名稱。添加注釋和文檔字符串為函數(shù)和復(fù)雜邏輯塊添加注釋說明其目的、參數(shù)、返回值和復(fù)雜度。def binary_search(arr, target): 在已排序數(shù)組arr中執(zhí)行二分查找尋找目標(biāo)值target。 參數(shù): arr (list): 一個(gè)已排序的列表。 target (int): 要查找的目標(biāo)值。 返回: int: 如果找到返回目標(biāo)值的索引否則返回-1。 時(shí)間復(fù)雜度: O(log n) 空間復(fù)雜度: O(1) # ... 實(shí)現(xiàn)代碼考慮邊界條件始終思考如果輸入是空列表、空鏈表、只有一個(gè)元素、目標(biāo)值不存在等情況你的代碼會(huì)怎樣測(cè)試驅(qū)動(dòng)在實(shí)現(xiàn)一個(gè)函數(shù)前先想好幾組測(cè)試用例正常、邊界、異常并在實(shí)現(xiàn)后運(yùn)行它們。7.2 復(fù)雜度分析練習(xí)每學(xué)一個(gè)新的數(shù)據(jù)結(jié)構(gòu)或算法嘗試自己分析其時(shí)間和空間復(fù)雜度。問自己代碼中有幾個(gè)循環(huán)它們嵌套嗎每個(gè)循環(huán)執(zhí)行了多少次與輸入規(guī)模n的關(guān)系分配了哪些額外的數(shù)據(jù)結(jié)構(gòu)7.3 下一步學(xué)習(xí)路線完成Week1的基礎(chǔ)后可以按以下路徑深入數(shù)據(jù)結(jié)構(gòu)深化學(xué)習(xí)雙向鏈表、循環(huán)鏈表、棧用數(shù)組/鏈表實(shí)現(xiàn)、隊(duì)列普通隊(duì)列、雙端隊(duì)列、優(yōu)先隊(duì)列。排序算法掌握選擇排序、插入排序然后學(xué)習(xí)更高效的歸并排序和快速排序并理解其分治思想。遞歸這是理解樹、圖以及許多高級(jí)算法如歸并排序、快速排序的關(guān)鍵。從計(jì)算階乘、斐波那契數(shù)列開始練習(xí)。抽象數(shù)據(jù)類型理解棧、隊(duì)列、集合、映射字典的抽象接口與不同實(shí)現(xiàn)如用鏈表實(shí)現(xiàn)棧。實(shí)踐平臺(tái)在LeetCode、HackerRank等平臺(tái)上從“Easy”難度的題目開始練習(xí)鞏固數(shù)組和鏈表的基本操作。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法就像學(xué)習(xí)樂理和指法初期可能會(huì)覺得枯燥但這是你未來構(gòu)建高效、優(yōu)雅程序大廈的基石。從理解每一個(gè)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的特性和代價(jià)開始多動(dòng)手實(shí)現(xiàn)多畫圖分析逐步培養(yǎng)出為問題選擇最佳工具的本能。