數(shù)據(jù)結構與算法（一），概述

轉載請注明出處：http://www.itdecent.cn/p/9f23c9604a2e

數(shù)據(jù)結構學了有一年的時間了，但是一直沒有好好的總結一下，現(xiàn)在回想起來，感覺好像都不怎么記得了。所以接下來一段時間我將重新學習一下，算是溫故而知新了。本著「分享是一種美德」的精神，我將把我的學習總結記錄下來，并與大家分享。

本節(jié)的主要內容有：

  • 一、數(shù)據(jù)結構
    • 1、定義
    • 2、關于數(shù)據(jù)結構的幾個術語
    • 3、邏輯結構與物理結構
  • 二、抽象數(shù)據(jù)類型
  • 三、算法
  • 四、算法的復雜度
    • 1、時間復雜度
    • 2、空間復雜度

一、數(shù)據(jù)結構

1、定義

數(shù)據(jù)結構是計算機存儲、組織數(shù)據(jù)的方式。在現(xiàn)實世界中，不同數(shù)據(jù)元素之間不是獨立的，而是存在特定關系的，我們將這些關系稱為結構。同樣在計算機中，數(shù)據(jù)元素也不是孤立、雜亂無序的，而是具有內在聯(lián)系的數(shù)據(jù)集合。

數(shù)據(jù)元素之間存在的一種或多種特定關系，也就是數(shù)據(jù)的組織形式，叫數(shù)據(jù)結構。也可以說，數(shù)據(jù)結構是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。

通常情況下，精心選擇的數(shù)據(jù)結構可以帶來更高的運行或者存儲效率。程序設計的實質就是數(shù)據(jù)結構和算法是設計，因此我們說程序設計 = 數(shù)據(jù)結構 + 算法。

2、關于數(shù)據(jù)結構的幾個術語

  • 數(shù)據(jù)：是描述客觀事物的符號，是計算機中可以操作的對象，是能被計算機識別，并輸入給計算機處理的符號集合。它不僅包括整型等數(shù)值類型，還包括字符、聲音、圖像等非數(shù)值類型。這些類型都具備兩個特征：

    • 可以輸入計算機
    • 能被計算機程序處理

  • 數(shù)據(jù)元素：是組成數(shù)據(jù)的、有一定意義的基本單位，在計算機中通常作為整體處理。也被稱為記錄。

  • 數(shù)據(jù)項：一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是A數(shù)據(jù)的不可分割的最小單位。。

  • 數(shù)據(jù)對象：是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。

例如：一本書的書目信息為一個數(shù)據(jù)元素，而書目信息的每一項（如書名、作者名等）為一個數(shù)據(jù)項。

3、邏輯結構與物理結構

按照不同的角度，數(shù)據(jù)結構可分為邏輯結構和物理結構。其中邏輯結構是面向問題的，而物理結構是面向計算機的，它們的基本目標都是將數(shù)據(jù)及其邏輯關系存儲到計算機內存中。

  • 邏輯結構：是指數(shù)據(jù)對象中數(shù)據(jù)元素之間的相互關系。分為四種：集合結構、線性結構、樹形結構和圖形結構。
四種邏輯結構
  • 物理（存儲）結構：是指數(shù)據(jù)的邏輯結構在計算機中的存儲形式。數(shù)據(jù)的存儲結構應正確反映數(shù)據(jù)元素之間的邏輯關系，這是關鍵。數(shù)據(jù)元素的存儲結構可分為兩種：順序存儲結構和鏈式存儲結構。
    • 順序存儲結構：把數(shù)據(jù)元素放在地址連續(xù)的存儲單元中，數(shù)據(jù)間的邏輯關系和物理關系一致。如，數(shù)組。
    • 鏈式存儲結構：把數(shù)據(jù)元素放在任意的存儲單元中，數(shù)據(jù)間使用指針關聯(lián)。數(shù)據(jù)元素的存儲關系不能反映其邏輯關系。如，鏈表。

二、抽象數(shù)據(jù)類型

數(shù)據(jù)類型是指一組性質相同的值的集合及定義在該集合上的一些操作的總稱。而抽象是指抽象出事物具有的普遍性的本質，它是抽出問題的特征而忽略非本質的細節(jié)，是對具體事物的一個概括。抽象隱藏了繁雜的細節(jié)，只保留實現(xiàn)目標所必須的信息。因此抽象數(shù)據(jù)類型可以定義為：

抽象數(shù)據(jù)類型（Abstract Data Type，ADT）是指一個數(shù)學模型及定義在該模型上的一組操作，它是一種向用例隱藏內部表示的數(shù)據(jù)類型。

面向對象編程的特征之一就是使用數(shù)據(jù)類型的實現(xiàn)封裝數(shù)據(jù)，以簡化實現(xiàn)、隔離用例開發(fā)、實現(xiàn)模塊化編程。抽象數(shù)據(jù)類型體現(xiàn)了程序設計中問題分解、抽象和信息隱藏的特性。它將實際生活中的問題分解為多個規(guī)模小、能夠獨立開發(fā)和調試的小型模塊，然后進行獨立編程。這種方式將代碼的影響限制在局部區(qū)域，改進了我們的軟件質量，促進了代碼復用。抽象數(shù)據(jù)類型抽象的層次越高，那么可復用性也越強。比如：java中的Object是對所有對象的抽象。

java中數(shù)據(jù)類型可以分為兩類：

java數(shù)據(jù)類型
  • 基本（原子）類型：不可以再分解的基本類型，包括int、short、long等
  • 引用（結構）類型：由其他類型組合而成，可以再分解。如，String、數(shù)組等

注意：

  1. 對原子類型的操作不一定是原子操作，這點并發(fā)編程時應特別注意。如，在32位機上對long類型的操作就不是原子操作，因為其高32位和低32位是分別存儲的。
  2. Java中所有的基本數(shù)據(jù)類型都有固定的存儲范圍和大小，其不受具體機器和操作系統(tǒng)的影響。

三、算法

算法（Algorithm)一詞最早出現(xiàn)在波斯數(shù)學家al-Khwarizmi所寫的《印度數(shù)字算術》中。歐幾里得算法（求兩個整數(shù)的最大公約數(shù)）被認為是史上第一個算法。

算法是解決特定問題求解步驟的描述，在計算機中表現(xiàn)為指令的有限序列，并且每條指令表示一個或多個操作。

算法的基本特性：

  • 輸入輸出，算法具有零個或多個輸入，至少有一個或多個輸出。
  • 有窮性，算法在執(zhí)行有限步后能夠自動結束，不會出現(xiàn)無限循環(huán)。
  • 確定性，算法的每一步都具有確定的含義，不會出現(xiàn)二義性。
  • 可行性，算法的每一步都能夠通過執(zhí)行有限次操作完成。

程序與算法的區(qū)別：

程序（program）是軟件開發(fā)人員根據(jù)用戶需求開發(fā)的、用程序設計語言描述的適合計算機執(zhí)行的指令（語句）序列。它包括「數(shù)據(jù)結構」、「算法」、「程序設計方法」和「編程語言」。程序是算法用某種程序設計語言的具體實現(xiàn)。程序可以不滿足算法的有窮性，比如操作系統(tǒng)也是一種程序，它可以一直運行。

算法的設計要求：

  • 正確性，算法至少應該具有輸入、輸出和加工處理無歧義、能正確反映問題的需求、能夠得到問題的正確答案。
  • 可讀性，便于閱讀、理解和交流。
  • 健壯性，輸入不合法時，算法能夠給出相應的處理，而不是產(chǎn)生錯誤的結果。
  • 高效性，算法應該盡量滿足高效率和低存儲的需求。

四、算法的復雜度

算法復雜度分為時間復雜度和空間復雜度。其作用： 時間復雜度是指執(zhí)行算法所需要的計算工作量；而空間復雜度是指執(zhí)行這個算法所需要的內存空間。

1、時間復雜度

算法的時間復雜度反映了算法執(zhí)行的時間長短，它是度量一個算法好壞的重要指標。

一般情況下，算法中基本操作重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)，用T(n)表示，若有某個輔助函數(shù)f(n),使得當n趨近于無窮大時，T(n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級函數(shù)。記作T(n)=O(f(n)),稱O(f(n)) 為算法的漸進時間復雜度，簡稱時間復雜度。

度量一個算法的時間復雜度通常有兩種方式：

  • 事后統(tǒng)計法
  • 事前分析法(大O表示法)

算法的時間復雜度是由最深層嵌套語句的頻度決定的。

大O表示法的推導：

  1. 用常數(shù)1取代運行時間中的所有加法常數(shù)
  2. 在修改后的運行次數(shù)函數(shù)中，只保留最高階
  3. 將最高階系數(shù)變?yōu)?

例1:

int i, j, temp;
for(i=0; i<n; i++) {
    for(j=i, j<n; j++) {
        temp++;
    }
}

語句執(zhí)行的總次數(shù)：

所以其時間復雜度為O(n^2)。

例2:

for(i=1;i<=n;i=i*2){
   System.out.println(i);
}

執(zhí)行的總次數(shù)滿足：

所以它的時間復雜度為O(logn)

例3：分析冒泡排序算法的時間復雜度

//冒泡排序算法
public static void bubbleSort(int[] data) {

    if (data == null) {
        return;
    }
    int temp = 0;
    for (int i = data.length - 1; i > 0; --i){
        for (int j = 0; j < i; ++j){
            if (data[j + 1] < data[j]){
                temp = data[j];
                data[j] = data[j + 1];
                data[j + 1] = temp;
            }
        }
    }
}

算法分析：

  • 最佳情況下（初始狀態(tài)是正序時），冒泡排序算法只需要一次掃描即可完成排序，此時比較次數(shù) C_min = n - 1，移動次數(shù) M_min = 0，所以時間復雜度為 O(n)
  • 最差情況下（初始狀態(tài)為逆序時），需要進行 n-1 次排序，每次排序進行 n-1 比較，此時比較次數(shù) C_max = n(n+1)/2，移動次數(shù) M_max = 3n(n+1)/2，所以時間復雜度為 O(n^2)

常見時間復雜度大小關系：

算法的時間復雜度和兩個因素有關：算法中的最大嵌套循環(huán)層數(shù)；最大嵌套循環(huán)結構中每次循環(huán)的次數(shù)。一般來說，具有多項式時間復雜度的算法是可以接受的；具有指數(shù)時間復雜度的算法，只有當n足夠小時才可以使用。一般效率較好的算法要控制在 O(N)或者O(log2 N)

2、空間復雜度

空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度，記做S(n)=O(f(n))。其中，n為問題規(guī)模，f(n)為語句關于n所占存儲空間的函數(shù)。

算法的空間復雜度分析方法和算法的時間復雜度分析方法基本相同。

例如:

int i, j, temp;
for(i=0; i<n; i++) {
    for(j=i, j<n; j++) {
        temp++;
    }
}

上方代碼中，僅需為變量 i、j、temp分配空間即可，所以空間復雜度 S(n) = O(1)。

參考

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

友情鏈接更多精彩內容