1. 2 知識應用

本節運用1. 1節所學知識來分析導學問題1中涉及的數據結構以及計算導學問題2的時間復雜度。

1.2.1 導學問題1-4、1-5和1-6的數據結構

對于導學問題1-4、1-5和1-6這幾個比較復雜的問題，先對其抽象出數學模型。

如圖1-11所示，在問題1-4中的學生成績表中，每個學生的學號、姓名、某門課程的成績稱為數據項，每個學生包含這些數據項的記錄稱為數據元素。所有數據元素（這個班級的學生）的集合就構成了一個數據對象。

將每一個數據元素看作一個結點，用圓圈表示，元素之間的邏輯關系用結點之間的連線表示，則問題就可以抽象成如圖1-12所示的一對一的線性邏輯結構。

在問題1-5中，把Linux系統中的文件、文件夾稱為數據元素，將每一個數據元素看作一個結點，用圓圈表示，元素之間的邏輯關系用結點之間的連線表示，則問題中的數據元素之間的關系就可以抽象成如圖1-13所示的樹形邏輯結構。本書將在第6章介紹“樹”這種抽象結構的存儲和操作實現。

在問題1-6中，數據元素之間的關系可以抽象成如圖1-14所示的圖結構。本書將在第7章介紹“圖”這種抽象結構的存儲和操作實現。

1.2.2 導學問題2的時間復雜度

由于循環語句的執行時間主要取決于循環體執行的次數，因此在分析循環語句時間復雜度時，更多關注的是循環體中基本語句執行的次數。

導學問題2的原始程序是一個雙重循環，其中外循環體中的語句p=1，執行次數為n；外循環體中的語句s+=p，執行次數為n；內循環體中語句p*=j，執行次數為1+2+3+…+n=n（n+1）/2；因此該程序的基本語句執行次數是n²數量級，時間復雜度T（n）=O（n²）。

改進后的程序是一個單重循環，循環體中的語句p*=j；和s+=p；分別執行了n次，因此該程序的基本語句執行次數是n數量級，時間復雜度T（n）=O（n）。

顯然，改進后的程序在時間復雜度上要比初始的程序好。