算法的概念是什么（什么是算法《算法和數據結構》）

fangxinyzj.com 2025-06-06 11:47:38

1、什么是算法

算法(algorithm):就是定義良好的計算過程，他取一個或一組的值為輸入，并產生出一個或一組值作為輸出。簡單來說算法就是一系列的計算步驟，用來將輸入數據轉化成輸出結果。

mark：我們可以把所有的算法想象為一本“菜譜”，特定的算法比如菜譜中的的一道“老醋花生米”的制作流程，只要按照菜譜的要求制作老醋花生米，那么誰都可以做出一道好吃的老醋花生米。so，這個做菜的步驟就可以理解為：“解決問題的步驟”

2、算法的意義

假設計算機無限快，并且計算機存儲容器是免費的，我們還需要各種亂七八糟的算法嗎？如果計算速度無限快，那么對于某一個問題來說，任何一個都可以解決他的正確方法都是可以的！

當然，計算機可以做到很快，但是不能做到無限快，存儲也可以很便宜但是不能做到免費。

那么問題就來了效率：解決同一個問題的各種不同算法的效率相差非常大，這種效率上的差距的影響往往比硬件和軟件方面的差距還要大。

3、如何選擇算法

第一要保證算法的正確性

一個算法對其每一個輸入的實例，都能輸出正確的結果并停止，則稱它是正確的，我們說一個正確的算法解決了給定的計算問題。不正確的算法對于某些輸入來說，可能根本不會停止，或者停止時給出的不是預期的結果。然而，與人們對不正確算法的看法相反，如果這些算法的錯誤率可以得到控制的話，它們有時候也是有用的。但是一般而言，我們還是僅關注正確的算法！

第二分析算法的時間復雜度

算法的時間復雜度反映了程序執行時間隨輸入規模增長而增長的量級，在很大程度上能很好反映出算法的好壞

數據結構與算法思維導圖

詳細教程資料+課件關注+后臺私信；資料；兩個字可以免費視頻領取+文檔+各大廠面試題資料內容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，嵌入式等。

1 算法的復雜度

1.1大O復雜度表示法

公式:

T(n)表示代碼執行的時間; n表示數據規模的大小; f(n) 表示每行代碼執行的次數總和。因為這是一個公式，所以用f(n)來表示。公式中的O,表示代碼的執行時間T(n)與f(n)表達式成正比。

所以，第一個例子中的T(n) = O(2n+2)，第二個例子中的T(m) = 0(2n2 +2n+3)。這就是大O時間復雜度表示法。大O時間復雜度實際上并不具體表示代碼真正的執行時間，而是表示代碼執行時間隨數據規模增長的變化趨勢，所以，也叫作漸進時間復雜度(asymptotic time complexity)，簡稱時間復雜度。

當n很大時，你可以把它想象成10000、100000。而公式中的低階、常量、系數三部分并不左右增長趨勢,所以都可以忽略。我們只需要記錄一個最大量級就可以了，如果用大O表示法表示剛講的那兩段代碼的時間復雜度,就可以記為: T(n) = O(n); T(n)= 0(n2)。

1.2.復雜度分析法則

1）單段代碼看高頻：比如循環。

2）多段代碼取最大：比如一段代碼中有單重循環和多重循環，那么取多重循環的復雜度。

3）嵌套代碼求乘積：比如遞歸、多重循環等

4）多個規模求加法：比如方法有兩個參數控制兩個循環的次數，那么這時就取二者復雜度相加。

1.3 時間復雜度分析

只關注循環執行次數最多的一段代碼

加法法則：總復雜度等于量級最大的那段代碼的復雜度

乘法法則：嵌套代碼的復雜度等于嵌套內外代碼復雜度的乘積

1.4 幾種常見事件復雜度實例分析

多項式階：隨著數據規模的增長，算法的執行時間和空間占用，按照多項式的比例增長。包括，

O(1)（常數階）、O(logn)（對數階）、O(n)（線性階）、O(nlogn)（線性對數階）、O(n^2)（平方階）、O(n^3)（立方階）

非多項式階：隨著數據規模的增長，算法的執行時間和空間占用暴增，這類算法性能極差。包括，

O(2^n)（指數階）、O(n!)（階乘階）

O(1) :

常量級時間復雜度,只要代碼的執行時間不隨 n 的增大而增長，這樣代碼的時間復雜度我們都記作 O(1)。

O(logn)、O(nlogn)


i=1;
while(i<=n) {
    i = i*2;
}

x=log2n，所以，這段代碼的時間復雜度就是 O(log2n)

O(m+n)、O(m*n)

int cal(int m, int n) {
      int sum_1=0;
      int i=1;
      for(;i<m;++i){
         sum_1 = sum_1 + i;
      }
      int sum_2 = 0;
      int j=1;
      for (;j<n;++j){
         sum_2 = sum_2 + j;
      }
      return sum_1 + sum_2;
   }

從代碼中可以看出，m和n是表示兩個數據規模。我們無法事先評估m和n誰的量級大，所以我們在表示復雜度的時候，就不能簡單地利用加法法則，省略掉其中一個。所以，上面代碼的時間復雜度就是0(m+n)。

針對這種情況，原來的加法法則就不正確了，我們需要將加法規則改為: T1(m) + T2(m) = O(f(m) + g(n))。但是乘法法則繼續有效: T1(m)*T2(n) = O(f(m) * f(n))。

1.5 空間復雜度分析

表示算法的存儲空間與數據規模之間的增長關系


void print(int n) {
    inti=0;
    int[] a = new int[n];
    for (i; i <n; ++i) {
        a[i] =i* i;
    }
    for(i=n-1;i>=0;--i){
        print out a[i]
    }
}

跟時間復雜度分析一樣，我們可以看到，第2行代碼中，我們申請了一個空間存儲變量i,但是它是最低階的，跟數據規模n沒有關系，所以我們可以忽略。第3行申請了一個大小為n的int類型數組，除此之外，剩下的代碼都沒有占用更多的空間，所以整段代碼的空間復雜度就是O(n)。

我們常見的空間復雜度就是O(1)、O(n)、 O(n2), 像O(logn)、O(nlogn) 這樣的對數階復雜度平時都用不到。而且，空間復雜度分析比時間復雜度分析要簡單很多。所以，對于空間復雜度，掌握剛才我說的這些內容已經足夠了。

1.6 復雜度增長趨勢圖:

最好情況時間復雜度、最壞時間復雜度、平均情況時間復雜度、均攤時間復雜度。

一、復雜度分析的4個概念

1.最壞情況時間復雜度：代碼在最壞情況下執行的時間復雜度。

2.最好情況時間復雜度：代碼在最理想情況下執行的時間復雜度。

3.平均時間復雜度：代碼在所有情況下執行的次數的加權平均值。

4.均攤時間復雜度：在代碼執行的所有復雜度情況中絕大部分是低級別的復雜度，個別情況是高級別復雜度且發生具有時序關系時，可以將個別高級別復雜度均攤到低級別復雜度上。基本上均攤結果就等于低級別復雜度。

二、為什么要引入這4個概念？

1.同一段代碼在不同情況下時間復雜度會出現量級差異，為了更全面，更準確地描述代碼的時間復雜度，所以引入這4個概念。

2.代碼復雜度在不同情況下出現量級差別時才需要區別這四種復雜度。大多數情況下，是不需要去分析它們的。

三、如何分析平均、均攤時間復雜度？

1.平均時間復雜度

代碼在不同情況下復雜度出現量級差別，則用代碼所有可能情況下執行次數的加權平均值表示。

2.均攤時間復雜度

兩個條件滿足時使用：1）代碼在絕大多數情況下是低級別復雜度，只有極少數情況是高級別復雜度；2）低級別和高級別復雜度出現具有時序規律。均攤結果一般都等于低級別復雜度。

1、數組

線性表: 線性表就是數據排成像一條線一樣的結構.每個線性表上的數據最多只有前和后兩個方向.常見的線性表結構：數組，鏈表、隊列、棧等。詳細教程資料+課件關注+后臺私信；資料；兩個字可以免費視頻領取+文檔+各大廠面試題資料內容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，嵌入式等。

什么是數組:

數組（Array）是一種線性表數據結構。它用一組連續的內存空間，來存儲一組具有相同類型的數據。

連續的內存空間和相同類型的數據(隨機訪問的前提)。

優點：兩限制使得具有隨機訪問的特性缺點：刪除，插入數據效率低。

對內存空間要求高，需要一塊連續的內存空間。

數組怎么根據下標隨機訪問的？

通過尋址公式：a[i]_address = base_address + i * data_type_size

其中data_type_size表示數組中每個元素的大小,base_address 是首元素地址,i數組下標。

為何數組插入和刪除低效：

插入：

若有一元素想往int[n]的第k個位置插入數據，需要在k-n的位置往后移。

最好情況時間復雜度 O(1)

如果數組中的數據不是有序的，也就是無規律的情況下，可以直接把第k個位置上的數據移到最后，然后將插入的數據直接放在第k個位置上。

最壞情況復雜度為O(n)

平均負責度為O(n)

2. 低效的插入和刪除

1）插入：從最好O(1) 最壞O(n) 平均O(n)

2）插入：數組若無序，插入新的元素時，可以將第K個位置元素移動到數組末尾，把心的元素，插入到第k個位置，此處復雜度為O(1)。

3）刪除：從最好O(1) 最壞O(n) 平均O(n)

4）多次刪除集中在一起，提高刪除效率

記錄下已經被刪除的數據，每次的刪除操作并不是搬移數據，只是記錄數據已經被刪除，當數組沒有更多的存儲空間時，再觸發一次真正的刪除操作。即JVM標記清除垃圾回收算法。

2、鏈表詳細教程資料+課件關注+后臺私信；資料；兩個字可以免費視頻領取+文檔+各大廠面試題資料內容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，嵌入式等。

什么是鏈表

1.和數組一樣，鏈表也是一種線性表。

2.從內存結構來看，鏈表的內存結構是不連續的內存空間，是將一組零散的內存塊串聯起來，從而進行數據存儲的數據結構。

3.鏈表中的每一個內存塊被稱為節點Node。節點除了存儲數據外，還需記錄鏈上下一個節點的地址，即后繼指針next。

鏈表的特點
詳細教程資料+課件關注+后臺私信；資料；兩個字可以免費視頻領取+文檔+各大廠面試題資料內容包括：C/C++，Linux，golang,Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，嵌入式等。

1.插入、刪除數據效率高O(1)級別（只需更改指針指向即可），隨機訪問效率低O(n)級別（需要從鏈頭至鏈尾進行遍歷）。

2.和數組相比，內存空間消耗更大，因為每個存儲數據的節點都需要額外的空間存儲后繼指針。

常用鏈表

1.單鏈表

1）每個節點只包含一個指針，即后繼指針。2）單鏈表有兩個特殊的節點，即首節點和尾節點。為什么特殊？用首節點地址表示整條鏈表，尾節點的后繼指針指向空地址null。3）性能特點：插入和刪除節點的時間復雜度為O（1），查找的時間復雜度為O(n)。

2.循環鏈表

1）除了尾節點的后繼指針指向首節點的地址外均與單鏈表一致。2）適用于存儲有循環特點的數據，比如約瑟夫問題。

3.雙向鏈表

1）節點除了存儲數據外，還有兩個指針分別指向前一個節點地址（前驅指針prev）和下一個節點地址（后繼指針next）。

2）首節點的前驅指針prev和尾節點的后繼指針均指向空地址。

3）性能特點：

和單鏈表相比，存儲相同的數據，需要消耗更多的存儲空間。

插入、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例，刪除操作分為2種情況：給定數據值刪除對應節點和給定節點地址刪除節點。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應節點進行刪除，時間復雜度為O(n)。對于第二種情況，要進行刪除操作必須找到前驅節點，單鏈表需要從頭到尾進行遍歷直到p->next = q，時間復雜度為O(n)，而雙向鏈表可以直接找到前驅節點，時間復雜度為O(1)。

對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p，每一次查詢時，根據要查找的值與p的大小關系，決定是往前還是往后查找，所以平均只需要查找一半的數據。

4.雙向循環鏈表：

首節點的前驅指針指向尾節點，尾節點的后繼指針指向首節點。

選擇數組還是鏈表？

1.插入、刪除和隨機訪問的時間復雜度數組：插入、刪除的時間復雜度是O(n)，隨機訪問的時間復雜度是O(1)。鏈表：插入、刪除的時間復雜度是O(1)，隨機訪問的時間復雜端是O(n)。

2.數組缺點

1）若申請內存空間很大，比如100M，但若內存空間沒有100M的連續空間時，則會申請失敗，盡管內存可用空間超過100M。

2）大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數據復制，而這時非常費時的。

3.鏈表缺點

1）內存空間消耗更大，因為需要額外的空間存儲指針信息。

2）對鏈表進行頻繁的插入和刪除操作，會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

4.如何選擇？

數組簡單易用，在實現上使用連續的內存空間，可以借助CPU的緩沖機制預讀數組中的數據，所以訪問效率更高，而鏈表在內存中并不是連續存儲，所以對CPU緩存不友好，沒辦法預讀。

如果代碼對內存的使用非常苛刻，那數組就更適合。

應用

1.如何分別用鏈表和數組實現LRU緩沖淘汰策略？

1）什么是緩存？

緩存是一種提高數據讀取性能的技術，在硬件設計、軟件開發中都有著非常廣泛的應用，比如常見的CPU緩存、數據庫緩存、瀏覽器緩存等等。

2）為什么使用緩存？即緩存的特點

緩存的大小是有限的，當緩存被用滿時，哪些數據應該被清理出去，哪些數據應該被保留？就需要用到緩存淘汰策略。

3）什么是緩存淘汰策略？

指的是當緩存被用滿時清理數據的優先順序。

4）有哪些緩存淘汰策略？

常見的3種包括先進先出策略FIFO（First In，First Out）、最少使用策略LFU（Least Frenquently Used）、最近最少使用策略LRU（Least Recently Used）。

5）鏈表實現LRU緩存淘汰策略

當訪問的數據沒有存儲在緩存的鏈表中時，直接將數據插入鏈表表頭，時間復雜度為O(1)；當訪問的數據存在于存儲的鏈表中時，將該數據對應的節點，插入到鏈表表頭,時間復雜度為O(n)。如果緩存被占滿，則從鏈表尾部的數據開始清理，時間復雜度為O(1)。

6）數組實現LRU緩存淘汰策略

方式一：首位置保存最新訪問數據，末尾位置優先清理

當訪問的數據未存在于緩存的數組中時，直接將數據插入數組第一個元素位置，此時數組所有元素需要向后移動1個位置，時間復雜度為O(n)；當訪問的數據存在于緩存的數組中時，查找到數據并將其插入數組的第一個位置，此時亦需移動數組元素，時間復雜度為O(n)。緩存用滿時，則清理掉末尾的數據，時間復雜度為O(1)。

方式二：首位置優先清理，末尾位置保存最新訪問數據

當訪問的數據未存在于緩存的數組中時，直接將數據添加進數組作為當前最有一個元素時間復雜度為O(1)；當訪問的數據存在于緩存的數組中時，查找到數據并將其插入當前數組最后一個元素的位置，此時亦需移動數組元素，時間復雜度為O(n)。緩存用滿時，則清理掉數組首位置的元素，且剩余數組元素需整體前移一位，時間復雜度為O(n)。（優化：清理的時候可以考慮一次性清理一定數量，從而降低清理次數，提高性能。）

2.如何通過單鏈表實現“判斷某個字符串是否為水仙花字符串”？（比如上海自來水來自海上）

1）前提：字符串以單個字符的形式存儲在單鏈表中。

2）遍歷鏈表，判斷字符個數是否為奇數，若為偶數，則不是。

3）將鏈表中的字符倒序存儲一份在另一個鏈表中。

4）同步遍歷2個鏈表，比較對應的字符是否相等，若相等，則是水仙花字串，否則，不是。

六、設計思想

時空替換思想：“用空間換時間” 與 “用時間換空間”

當內存空間充足的時候，如果我們更加追求代碼的執行速度，我們就可以選擇空間復雜度相對較高，時間復雜度小相對較低的算法和數據結構，緩存就是空間換時間的例子。如果內存比較緊缺，比如代碼跑在手機或者單片機上，這時，就要反過來用時間換空間的思路。

3、隊列

什么是隊列:

隊列是一種受限的線性表數據結構,只支持兩個操作:入棧push()和出棧pop0,隊列跟非常相似,支持的操作也 ,很有限,最基本的操作也是兩個:入隊enqueue(),放一個數據到隊列尾部;出隊dequeue0),從隊列頭部取一個元素。

特點:

1 . 隊列跟棧一樣,也是一種抽象的數據結構。

2. 具有先進先出的特性,支持在隊尾插入元素,在隊頭刪除元素。

實現:

隊列可以用數組來實現,也可以用鏈表來實現。

用數組實現的隊列叫作順序隊列,用鏈表實現的隊列叫作鏈式隊列。

基于數組的隊列:

實現思路:

實現隊列需要兩個指針:一個是head指針,指向隊頭;一個是tail指針,指向隊尾。你可以結合下面這幅圖來理解。當a,b,c,d依次入隊之后,隊列中的head指針指向下標為0的位置, tail指針指向下標為4的位置。

當我們調用兩次出隊操作之后,隊列中head指針指向下標為2的位置, tail指針仍然指向下標為4的位置.

隨著不停地進行入隊、出隊操作, head和tail都會持續往后移動。當tail以 . ,動到最右邊,即使數組中還有空閑空間,也無法繼續往隊列中添加數據了。這個問題該如何解決呢?

在出隊時可以不用搬移數據。如果沒有空閑空間了,我們只需要在入隊時,再集中出發 ,發一次數據的搬移操作。

當隊列的tail指針移動到數組的最右邊后,如果有新的數據入隊,我們可以將 head到tail之間的數據,整體搬移到數組中0到tail-head的位置。

基于鏈表的實現:

需要兩個指針: head指針和tail指針,它們分別指向鏈表的第一個結,點和最后一個結點。

如圖所示,入隊時, tail->next= new node, tail = tail->next:出隊時, head = head->next.

天天色综合色,多姿,japanese 吃奶free,韩国欧洲一级毛片免费,亚洲精品成人区在线观看

算法的概念是什么（什么是算法《算法和數據結構》）

數據結構與算法思維導圖

1 算法的復雜度

1.1大O復雜度表示法

總結;

算法的概念是什么（什么是算法《算法和數據結構》）

為您推薦

數據結構與算法思維導圖

1 算法的復雜度

1.1大O復雜度表示法

總結;

相關文章