日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
數(shù)據(jù)結(jié)構(gòu)—動態(tài)數(shù)組和時(shí)間復(fù)雜度分析

一、數(shù)組基礎(chǔ)

1.1 定義

數(shù)組(Array)是一種線性表數(shù)據(jù)結(jié)構(gòu)，它用一組連續(xù)的內(nèi)存空間來存儲一組具有相同類型的數(shù)據(jù)。

創(chuàng)新互聯(lián)建站專注于企業(yè)營銷型網(wǎng)站、網(wǎng)站重做改版、彌渡網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5頁面制作、商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站制作、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為彌渡等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

1.2 創(chuàng)建流程

當(dāng)我們在 java 中當(dāng)創(chuàng)建一個(gè)數(shù)組時(shí)，會在內(nèi)存中劃分出一塊 連續(xù)的內(nèi)存，當(dāng)有數(shù)據(jù)進(jìn)入的時(shí)候會將數(shù)據(jù) 按順序的存儲在這塊連續(xù)的內(nèi)存中。當(dāng)需要讀取數(shù)組中的數(shù)據(jù)時(shí)，需要提供數(shù)組中的 索引，然后數(shù)組根據(jù)索引將內(nèi)存中的數(shù)據(jù)取出來，返回給讀取程序。

把數(shù)據(jù)碼成一排進(jìn)行存放：

所有的數(shù)據(jù)結(jié)構(gòu)都支持幾個(gè)基本操作：讀取、插入、刪除數(shù)組索引可以有語意，也可以沒有語意，比如說 student[2]，就代表是這個(gè)數(shù)組中的第三個(gè)學(xué)生。

因?yàn)閿?shù)組在存儲數(shù)據(jù)時(shí)是按順序存儲的，存儲數(shù)據(jù)的內(nèi)存也是連續(xù)的，所以數(shù)組最大的優(yōu)點(diǎn)就是能夠 快速查詢，尋址讀取數(shù)據(jù)比較容易，但是插入和刪除就比較困難。

為什么數(shù)組最大的優(yōu)點(diǎn)就是能夠 快速查詢。因?yàn)楫?dāng)我們在讀取數(shù)據(jù)時(shí)，只需要告訴數(shù)組獲取數(shù)據(jù)的索引位置就可以了，數(shù)組就會把對應(yīng)位置的數(shù)據(jù)，讀取出來

插入和 刪除比較困難是因?yàn)檫@些存儲數(shù)據(jù)的內(nèi)存是連續(xù)的，數(shù)組大小固定，插入和刪除都需要移動元素

例如：一個(gè)數(shù)組中編號 0>1>2>3>4這五個(gè)內(nèi)存地址中都存了數(shù)組的數(shù)據(jù)，但現(xiàn)在你需要往4中插入一個(gè)數(shù)據(jù)，那就代表著從4開始，后面的所有內(nèi)存中的數(shù)據(jù)都要往后移一個(gè)位置。

二、編寫我們自己的數(shù)組類

我們知道想要維護(hù)某一個(gè)數(shù)據(jù)，我們需要對這個(gè)數(shù)據(jù)有這最基本的 增、刪、改、查，這幾個(gè)基本功能，所以我們自己手動編寫的數(shù)組類，也是需要有用這幾個(gè)最基本的功能，雖然不會像 List、Map這些類，那么強(qiáng)大，但是對于我們普通的開發(fā)來說，基本是可以滿足，下圖所示就是我們一個(gè)基本的數(shù)組類，那么我們是如何對數(shù)組進(jìn)行改造，來編寫一個(gè)屬于我們自己的數(shù)組類的呢，這里我們以 增加和刪除做重點(diǎn)講解，本文中的所有源碼會在最后貼出來，請往下看。

從上圖中我們可以得知，我們創(chuàng)建數(shù)組類的時(shí)候，需要三個(gè)元素 data、size、capacity，而我們所需要使用的數(shù)組，肯定是要能夠支持 多種數(shù)據(jù)類型，而不是單一的數(shù)據(jù)結(jié)構(gòu)，因此，我們可以在設(shè)計(jì)類的時(shí)候，是需要加上泛型支持，讓我們的數(shù)據(jù)結(jié)構(gòu)可以支持放置 任何數(shù)據(jù)類型。

data：需要傳遞的數(shù)據(jù)size：元素中的個(gè)數(shù)capacity：數(shù)組的初始容量

注意：我們上面所說的放置 任何數(shù)據(jù)類型，只能是類對象，不可以是基本數(shù)據(jù)類型，但是我們每個(gè)基本數(shù)據(jù)類型都有對應(yīng)的包裝類，所以我們的基本類型也是可以使用的，不過只是使用的是它的包裝類

因此，我們在設(shè)計(jì)我們的數(shù)組類的時(shí)候，我們可以這么設(shè)計(jì)

 
 
 
 
    
  
  
  
  
  1. /**
    2. 
  
  
  
  
  2.  * @program: 
    3. 
  
  
  
  
  3.  * @ClassName ArrayPlus
    4. 
  
  
  
  
  4.  * @description:
    5. 
  
  
  
  
  5.  * @author: lyy
    6. 
  
  
  
  
  6.  * @create: 2019-11-18 22:27
    7. 
  
  
  
  
  7.  * @Version 1.0
    8. 
  
  
  
  
  8.  **/
    9. 
  
  
  
  
  9. public class ArrayPlus {
    10. 
  
  
  
  
  10. 
  
  
  
  
  11.     private E[] data;
    12. 
  
  
  
  
  12.     private int size;
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.     //構(gòu)造函數(shù)，傳入數(shù)組的容量capacity 構(gòu)造array
    15. 
  
  
  
  
  15.     public ArrayPlus(int capacity){
    16. 
  
  
  
  
  16.         data = (E[])new Object[capacity];
    17. 
  
  
  
  
  17.         size = 0;
    18. 
  
  
  
  
  18.     }
    19. 
  
  
  
  
  19.     //無參數(shù)的構(gòu)造函數(shù)，傳入數(shù)組的容量capacity=10
    20. 
  
  
  
  
  20.     public ArrayPlus(){
    21. 
  
  
  
  
  21.         this(10);
    22. 
  
  
  
  
  22.     }
    23. 
  
  
  
  
  23. 
  
  
  
  
  24.     //獲取元素中的個(gè)數(shù)
    25. 
  
  
  
  
  25.     public int getSize(){
    26. 
  
  
  
  
  26.         return size;
    27. 
  
  
  
  
  27.     }
    28. 
  
  
  
  
  28. 
  
  
  
  
  29.     //獲取數(shù)組的容量
    30. 
  
  
  
  
  30.     public int getCapacity(){
    31. 
  
  
  
  
  31.         return data.length;
    32. 
  
  
  
  
  32.     }
    33. 
  
  
  
  
  33. 
  
  
  
  
  34.     //返回?cái)?shù)組是否為空
    35. 
  
  
  
  
  35.     public boolean isEmpty(){
    36. 
  
  
  
  
  36.         return size == 0;
    37. 
  
  
  
  
  37.     }
    38. 
  
  
  
  
  38. 
  
  
  
  
  39.     @Override
    40. 
  
  
  
  
  40.     public String toString(){
    41. 
  
  
  
  
  41.         StringBuffer res = new StringBuffer();
    42. 
  
  
  
  
  42.         res.append(String.format("Array：Size = %d，capacity = %d\n",size,data.length));
    43. 
  
  
  
  
  43.         res.append("[");
    44. 
  
  
  
  
  44.         for (int i = 0; i < size; i++) {
    45. 
  
  
  
  
  45.             res.append(data[i]);
    46. 
  
  
  
  
  46.             if(i != size - 1)
    47. 
  
  
  
  
  47.                 res.append("，");
    48. 
  
  
  
  
  48.         }
    49. 
  
  
  
  
  49.         res.append("]");
    50. 
  
  
  
  
  50.         return res.toString();
    51. 
  
  
  
  
  51.     }
    52. 
  
  
  
  
  52. 
  
  
  
  
  53. }
    54.

2.1 數(shù)組添加元素

在數(shù)組中是如何添加數(shù)據(jù)的呢，首先我們需要創(chuàng)建一個(gè) 擁有初始容量的數(shù)組，當(dāng)我們創(chuàng)建完成之后，size是指向第一個(gè)元素的，也就是 index=0的地方，當(dāng)我們添加第一個(gè)數(shù)據(jù)后 也就是 data[0]=12后，我們的元素中的個(gè)數(shù) size，需要往后挪一位的，也就是 size++的操作，每當(dāng)我們操作一位，就需要將上面的操作重復(fù)執(zhí)行，直到最后一個(gè)元素添加到我們的數(shù)組中。

如下圖所示：

知道了怎么操作，但是我們要如果通過代碼來完成呢?

首先我們要清楚在添加的時(shí)候， 在哪里?添加什么數(shù)據(jù)?，在哪里：我們要在數(shù)據(jù)的什么地方進(jìn)行添加，也就是要添加到數(shù)組中的哪個(gè)下標(biāo)—— index的地方，知道了在下標(biāo)，我們只需要將添加的數(shù)據(jù)，添加到數(shù)組中為 index 的地方即可，除此之外，我們只需要對添加時(shí)，做一些基本的判斷就可以了，代碼如下：

 
 
 
 
    
  
  
  
  
  1. //在所有元素后添加一個(gè)新元素
    2. 
  
  
  
  
  2.   public void addLast(E e){
    3. 
  
  
  
  
  3.       add(size,e);
    4. 
  
  
  
  
  4.   }
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.   //想所有元素前添加一個(gè)新元素
    7. 
  
  
  
  
  7.   public void addFirst(E e){
    8. 
  
  
  
  
  8.       add(0,e);
    9. 
  
  
  
  
  9.   }
    10. 
  
  
  
  
  10. 
  
  
  
  
  11.   //在第Index個(gè)位置插入一個(gè)新元素e
    12. 
  
  
  
  
  12.   public void add(int index,E e){
    13. 
  
  
  
  
  13.       if(size == data.length)
    14. 
  
  
  
  
  14.           throw new IllegalArgumentException("Add failed . Array is full.");
    15. 
  
  
  
  
  15. 
  
  
  
  
  16.       if(index < 0 || index > size)
    17. 
  
  
  
  
  17.           throw new IllegalArgumentException("Add failed . Require index < 0 || index > size.");
    18. 
  
  
  
  
  18. 
  
  
  
  
  19.       for (int i = size - 1; i >= index ; i--)
    20. 
  
  
  
  
  20.           data[i+1] = data[i];
    21. 
  
  
  
  
  21. 
  
  
  
  
  22.       data[index]  = e;
    23. 
  
  
  
  
  23.       size++;
    24. 
  
  
  
  
  24.   }
    25.

測試代碼：

 
 
 
 
    
  
  
  
  
  1. public class Main2 {
    2. 
  
  
  
  
  2. 
  
  
  
  
  3.     public static void main(String[] args) {
    4. 
  
  
  
  
  4.         ArrayPlus arr = new ArrayPlus<>();
    5. 
  
  
  
  
  5.         for (int i = 12; i < 16; i++)
    6. 
  
  
  
  
  6.             arr.addLast(i);
    7. 
  
  
  
  
  7.         System.out.println(arr);
    8. 
  
  
  
  
  8.     }
    9. 
  
  
  
  
  9. }
    10.

返回結(jié)果：

 
 
 
 
    
  
  
  
  
  1. Array：Size = 4，capacity = 10
    2. 
  
  
  
  
  2. [12，13，14，15]
    3.

在數(shù)組中是如何執(zhí)行插入呢?如下圖所示：

測試代碼：

 
 
 
 
    
  
  
  
  
  1. public static void main(String[] args) {
    2. 
  
  
  
  
  2. 
  
  
  
  
  3.        ArrayPlus arr = new ArrayPlus<>();
    4. 
  
  
  
  
  4.        for (int i = 12; i < 16; i++)
    5. 
  
  
  
  
  5.            arr.addLast(i);
    6. 
  
  
  
  
  6.        System.out.println(arr);
    7. 
  
  
  
  
  7. 
  
  
  
  
  8.        arr.add(1,100);
    9. 
  
  
  
  
  9.        System.out.println(arr);
    10. 
  
  
  
  
  10. 
  
  
  
  
  11. 
  
  
  
  
  12.    }
    13.

返回結(jié)果：

 
 
 
 
    
  
  
  
  
  1. Array：Size = 4，capacity = 10
    2. 
  
  
  
  
  2. [12，13，14，15]
    3. 
  
  
  
  
  3. Array：Size = 5，capacity = 10
    4. 
  
  
  
  
  4. [12，100，13，14，15]
    5.

2.2 數(shù)組刪除元素

如果我們想要刪除 索引為1的元素，是怎樣操作的呢，首先我們需要先將 索引為2的數(shù)據(jù)，覆蓋到 索引為1的元素上，再將 索引為3的數(shù)據(jù)放到 索引為2上，依次循環(huán)操作，直到最后一位元素，我們在將最后一位元素的數(shù)據(jù)設(shè)置為 null，這樣垃圾回收機(jī)制就會自動幫我們清除這個(gè)元素。整個(gè)過程就完成了刪除元素的功能，具體流程如下圖所示：

實(shí)現(xiàn)代碼：

 
 
 
 
    
  
  
  
  
  1. //查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1
    2. 
  
  
  
  
  2.     public int find(E e){
    3. 
  
  
  
  
  3.         for (int i = 0; i < size; i++) {
    4. 
  
  
  
  
  4.             if(data[i].equals(e))
    5. 
  
  
  
  
  5.                 return i;
    6. 
  
  
  
  
  6.         }
    7. 
  
  
  
  
  7.         return -1;
    8. 
  
  
  
  
  8.     }
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.  //從數(shù)組中刪除index位置的元素，返回刪除的元素
    11. 
  
  
  
  
  11.     public E remove(int index){
    12. 
  
  
  
  
  12.         if(index < 0 || index >= size)
    13. 
  
  
  
  
  13.             throw new IllegalArgumentException("remove failed . Index is illegal.");
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.         E ret = data[index];
    16. 
  
  
  
  
  16.         for (int i = index+1 ; i < size; i++)
    17. 
  
  
  
  
  17.                 data[i - 1] = data[i];
    18. 
  
  
  
  
  18. 
  
  
  
  
  19.         size--;
    20. 
  
  
  
  
  20.         // loitering objects != memory leak
    21. 
  
  
  
  
  21.         data[size] = null;//如果一旦使用新的元素，添加新的對象就會覆蓋掉
    22. 
  
  
  
  
  22.         return ret;
    23. 
  
  
  
  
  23.     }
    24. 
  
  
  
  
  24. 
  
  
  
  
  25.     //從數(shù)組中刪除第一個(gè)位置的元素，返回刪除的元素
    26. 
  
  
  
  
  26.     public E removeFirst(){
    27. 
  
  
  
  
  27.         return remove(0);
    28. 
  
  
  
  
  28.     }
    29. 
  
  
  
  
  29. 
  
  
  
  
  30.     //從數(shù)組中刪除最后一個(gè)位置的元素，返回刪除的元素
    31. 
  
  
  
  
  31.     public E removeLast(){
    32. 
  
  
  
  
  32.         return remove(size-1);
    33. 
  
  
  
  
  33.     }
    34. 
  
  
  
  
  34. 
  
  
  
  
  35.     //從數(shù)組中刪除元素e
    36. 
  
  
  
  
  36.     public void removeElement(E e){
    37. 
  
  
  
  
  37.         int index = find(e);
    38. 
  
  
  
  
  38.         if(index != -1)
    39. 
  
  
  
  
  39.             remove(index);
    40. 
  
  
  
  
  40. 
  
  
  
  
  41.     }
    42.

測試：

 
 
 
 
    
  
  
  
  
  1. import com.bj.array.ArrayPlus;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. public class Main2 {
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.     public static void main(String[] args) {
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.         ArrayPlus arr = new ArrayPlus<>();
    8. 
  
  
  
  
  8.         for (int i = 12; i < 16; i++)
    9. 
  
  
  
  
  9.             arr.addLast(i);
    10. 
  
  
  
  
  10.         System.out.println(arr);
    11. 
  
  
  
  
  11. 
  
  
  
  
  12.         arr.add(1,100);
    13. 
  
  
  
  
  13.         System.out.println(arr);
    14. 
  
  
  
  
  14. 
  
  
  
  
  15.         arr.remove(1);
    16. 
  
  
  
  
  16.         System.out.println(arr);
    17. 
  
  
  
  
  17. 
  
  
  
  
  18. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20. 
  
  
  
  
  21. }
    22.

返回示例：

 
 
 
 
    
  
  
  
  
  1. Array：Size = 4，capacity = 10
    2. 
  
  
  
  
  2. [12，13，14，15]
    3. 
  
  
  
  
  3. Array：Size = 5，capacity = 10
    4. 
  
  
  
  
  4. [12，100，13，14，15]
    5. 
  
  
  
  
  5. Array：Size = 4，capacity = 10
    6. 
  
  
  
  
  6. [12，13，14，15]
    7.

我們看到結(jié)果已經(jīng)把索引為1的刪除了，到這里我們已經(jīng)完成了一大半了，還有一小點(diǎn)也是最重要的，就是當(dāng)我們添加數(shù)據(jù)超過了我們的初始容量大小的時(shí)候，就會報(bào)錯(cuò)，初始容量，無法添加超過的數(shù)據(jù)，那么我們應(yīng)該怎么操作呢?其實(shí)很簡單，我們只需要給我們數(shù)組類，添加一個(gè)擴(kuò)容的方法即可，當(dāng)我們元素的個(gè)數(shù)等于數(shù)組長度的時(shí)候，我們就進(jìn)行擴(kuò)容，我們稱之為 動態(tài)數(shù)組。

2.3 動態(tài)數(shù)組

前邊我們講過的用new給基本類型和對象在運(yùn)行時(shí)分配內(nèi)存，但它們的已經(jīng)在編譯時(shí)就已經(jīng)確定下來，因?yàn)槲覀優(yōu)橹暾垉?nèi)存的數(shù)據(jù)類型在程序里有明確的定義，有明確的單位長度。　　但是，總有些時(shí)候，必須要等到程序運(yùn)行時(shí)才能確定需要申請多少內(nèi)存，甚至還需要根據(jù)程序的運(yùn)行情況追加申請更多的內(nèi)存。從某種意義上講，這樣的內(nèi)存管理才是真正的動態(tài)。下面，我將帶大家編寫一個(gè)程序?yàn)橐粋€(gè)整數(shù)型數(shù)組分配內(nèi)存，實(shí)現(xiàn)動態(tài)數(shù)組?！　‘?dāng)你們看到下面這個(gè)圖的時(shí)候，有沒有想到什么，沒錯(cuò)，有點(diǎn)像C++里面的指針

實(shí)現(xiàn)代碼：

 
 
 
 
    
  
  
  
  
  1. //在第Index個(gè)位置插入一個(gè)新元素e
    2. 
  
  
  
  
  2.    public void add(int index,E e){
    3. 
  
  
  
  
  3. 
  
  
  
  
  4.        if(index < 0 || index > size)
    5. 
  
  
  
  
  5.            throw new IllegalArgumentException("Add failed . Require index < 0 || index > size.");
    6. 
  
  
  
  
  6. 
  
  
  
  
  7.        if(size == data.length)
    8. 
  
  
  
  
  8.            resize(2 * data.length);
    9. 
  
  
  
  
  9. 
  
  
  
  
  10. 
  
  
  
  
  11.        for (int i = size - 1; i >= index ; i--)
    12. 
  
  
  
  
  12.            data[i+1] = data[i];
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.        data[index]  = e;
    15. 
  
  
  
  
  15.        size++;
    16. 
  
  
  
  
  16.    }
    17. 
  
  
  
  
  17. 
  
  
  
  
  18.    private void resize(int newCapacity) {
    19. 
  
  
  
  
  19.        E[] newData = (E[])new Object[newCapacity];
    20. 
  
  
  
  
  20.        for (int i = 0; i < size; i++)
    21. 
  
  
  
  
  21.            newData[i] = data[i];
    22. 
  
  
  
  
  22.        data = newData;
    23. 
  
  
  
  
  23.    }
    24.

動態(tài)數(shù)組測試：

 
 
 
 
    
  
  
  
  
  1. import com.bj.array.ArrayPlus;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. public class Main2 {
    4. 
  
  
  
  
  4. 
  
  
  
  
  5.     public static void main(String[] args) {
    6. 
  
  
  
  
  6.         ArrayPlus arr = new ArrayPlus<>();
    7. 
  
  
  
  
  7.         for (int i = 0; i < 10; i++)
    8. 
  
  
  
  
  8.             arr.addLast(i);
    9. 
  
  
  
  
  9.         System.out.println(arr);
    10. 
  
  
  
  
  10. 
  
  
  
  
  11.         arr.add(1,100);
    12. 
  
  
  
  
  12.         System.out.println(arr);
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.         for (int i = 0; i < 6; i++)
    15. 
  
  
  
  
  15.             arr.remove(i);
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.         arr.removeLast();
    18. 
  
  
  
  
  18.         System.out.println(arr);
    19. 
  
  
  
  
  19.     }
    20. 
  
  
  
  
  20. }
    21.

測試結(jié)果：

 
 
 
 
    
  
  
  
  
  1. Array：Size = 10，capacity = 10
    2. 
  
  
  
  
  2. [0，1，2，3，4，5，6，7，8，9]
    3. 
  
  
  
  
  3. Array：Size = 11，capacity = 20
    4. 
  
  
  
  
  4. [0，100，1，2，3，4，5，6，7，8，9]
    5. 
  
  
  
  
  5. Array：Size = 4，capacity = 10
    6. 
  
  
  
  
  6. [100，2，4，6]
    7.

從結(jié)果中我們可以看到，當(dāng)我們數(shù)組元素超過初始容量大小時(shí)，自動擴(kuò)容到初始容量的 兩倍也就是20，當(dāng)我們數(shù)組長度小于1/4的時(shí)候，為什么是1/4的時(shí)候而不是1/2的時(shí)候呢，下面我們會做詳細(xì)介紹。當(dāng)我們數(shù)組長度小于1/4的時(shí)候，會自動縮回到初始10的容量，不會去占據(jù)大量的內(nèi)存空間。

三、時(shí)間復(fù)雜度分析

3.1 基礎(chǔ)

五種常見的時(shí)間復(fù)雜度 1) O(1)：常數(shù)復(fù)雜度, 最快的算法，數(shù)組的存取是O(1) 1) O(n)：線性復(fù)雜度, 例如：數(shù)組, 以遍歷的方式在其中查找元素 1) O(logN)：對數(shù)復(fù)雜度 1) O(nlogn)：求兩個(gè)數(shù)組的交集, 其中一個(gè)是有序數(shù)組，A數(shù)組每一個(gè)元素都要在B數(shù)組中進(jìn)行查找操作，每次查找如果使用二分法則復(fù)雜度是 logN 1) O(n2)：平方復(fù)雜度，求兩個(gè)無序數(shù)組的交集

在這里，大O描述的是算法的運(yùn)行時(shí)間和輸入數(shù)據(jù)之間的關(guān)系

3.2 舉例說明

大家可以看下面一個(gè)例子

 
 
 
 
    
  
  
  
  
  1. public static int sum(int[] nums){
    2. 
  
  
  
  
  2.   int sum = 0;
    3. 
  
  
  
  
  3.   for(int num: nums) sum += num;
    4. 
  
  
  
  
  4.   return sum;
    5. 
  
  
  
  
  5. }
    6.
  • 這個(gè)算法是 O(n) 復(fù)雜度的，其中 n是nums中的元素個(gè)數(shù)，算法和n呈線性關(guān)系
  • 為什么說他是 O(n)的時(shí)間復(fù)雜度呢，因?yàn)檫@個(gè)算法運(yùn)行的時(shí)間的多少是和 nums中元素的個(gè)數(shù)成線性關(guān)系的，那么這個(gè)線性關(guān)系，表現(xiàn)在我們的 n 是一次方，它不是 O(n) 方的，也不是 O(n) 的立方，n 對應(yīng)的是一次方。
  • 我們忽略常數(shù)，實(shí)際時(shí)間是：T=c1*n+c2c1：我們要把這個(gè)數(shù)據(jù)從 nums數(shù)組中取出來，其次我們還要把 sum這個(gè)數(shù)取出來，然后 num這個(gè)數(shù)和 sum相加，最終呢我們要這個(gè)結(jié)果扔回給 sum中c2：開始開辟了一個(gè)Int型的空間，我們把它叫 sum ，要把 0 初始化賦值給sum，在最終呢我們還要把這個(gè) sum 給 return 回去

一方面把 c1 和 c2 具體分析出來是不大必要的，另一方面也是不太可能的，為什么說不可能呢?如果說把 num 從 nums 中取出來，基于 不同的語言，基于 不同的實(shí)現(xiàn)，它實(shí)際運(yùn)行的 時(shí)間是不等的，就算轉(zhuǎn)換成機(jī)器碼，它對應(yīng)的機(jī)器碼的指令數(shù)也有可能是不同的，就算是指令數(shù)是相同的，同樣的一個(gè)指令，在我們 cpu 的底層，你使用的 cpu 不同，很有可能，執(zhí)行的操作也是不同的，所以在實(shí)際上我們可能說出 c1 是幾條指令，但是卻很難說出 c1 到底是多少，c2也是同理，正因?yàn)槿绱?，我們在進(jìn)行時(shí)間復(fù)雜度時(shí)，是忽略這些常數(shù)的。

忽略這些常數(shù)就意味著什么，就意味著這些 t=2*n+2和t=2000*n+10000算法這些都是 O(n) 的算法，見下面列表：換句話說他們都是線性數(shù)據(jù)的算法，也就是說我們這個(gè)算法消耗的時(shí)間是和我們輸入數(shù)據(jù)的規(guī)模成一個(gè)線性相關(guān)的， t=1*n*n+0也線性算法是和我們成平方關(guān)系的 ，他的性能比上面的差，因?yàn)樗?O(n^2)的

O(n)和O(n^2)并不代表說 O(n)的算法快于 O(n^2)的算法，我們要看 n 的常數(shù)，比如 n=3000的時(shí)候，或者 n>3000的時(shí)候， O(n^2)消耗的時(shí)間是遠(yuǎn)遠(yuǎn)大于 O(n)的，n越大 O(n)遠(yuǎn)遠(yuǎn)快于 O(n^2)O：描述的是一個(gè)算法，也就是說漸進(jìn)時(shí)間復(fù)雜度當(dāng)高階項(xiàng)和低階項(xiàng)同時(shí)出現(xiàn)的時(shí)候，低階項(xiàng)會被忽略，比如說：T=2*n*n+300n+10當(dāng)中 2*n*n，是 O(n^2)級別的算法，屬于高階項(xiàng)， 300n是 O(n)的算法低階項(xiàng)，當(dāng)n無窮大的時(shí)候，低階項(xiàng)起的作用很小。

3.3 分析動態(tài)數(shù)組的時(shí)間復(fù)雜度

3.3.1 添加操作

添加操作 總體來說屬于 O(n) 級別的復(fù)雜度，如下列表

在程序設(shè)計(jì)中，我們要采用最嚴(yán)謹(jǐn)?shù)脑O(shè)計(jì)，需要考慮到最壞的情況，所以我們說添加操作時(shí)屬于 O(n)級別的復(fù)雜度，是因?yàn)槲覀冊?addLast的時(shí)候，有可能會進(jìn)行 resize的操作，我們從最壞的情況分析是對的，但是 addLast不可能每次都是進(jìn)行 resize操作，比如 size 有十個(gè)，我們要添加十個(gè)元素后才會觸發(fā)一個(gè) resize,我們要在添加十個(gè)元素才會觸發(fā)一個(gè) resize，因此我們使用最壞情況進(jìn)行分析的是不合理的，那么分析 addLast時(shí)間復(fù)雜度呢，請看下面小節(jié)。

3.3.2 resize的復(fù)雜度分析

總共進(jìn)行了17次基本操作：9次添加操作8次元素轉(zhuǎn)移操作

  • 9次addLast操作，觸發(fā)resize，總共進(jìn)行了17次基本操作，平均每次addLast操作，進(jìn)行了2次基本操作
  • 假設(shè) capacity = n，n+1 次addLast，觸發(fā)resize，總共進(jìn)行了2n+1次基本操作，平均，每次addLast操作，進(jìn)行了2次基本操作
  • 這樣均攤計(jì)算，時(shí)間復(fù)雜度是O(1)的，在這個(gè)例子里，這樣均攤計(jì)算，比計(jì)算最壞情況有意義
  • addLast 均攤復(fù)雜度是O(1)的，同理我們看 removeLast操作，均攤復(fù)雜度也是O(1)

3.3.3 復(fù)雜度震蕩

當(dāng)我們數(shù)組容量滿了的時(shí)候，因?yàn)槭莿討B(tài)數(shù)組，回去自動擴(kuò)容，我們又馬上去remove 一個(gè)操作的時(shí)候，因?yàn)閿?shù)組容量小于 初始容量的一半的時(shí)候，又會 自動 resize縮減為一半的大小，如此操作，就會一個(gè)問題，就是我們在 removeLast的時(shí)候 resize 過于著急(Eager)

解決方案：Lazy，懶散的，其實(shí)也很簡單，如下圖所示：

當(dāng)我們的 size == capacity /4 時(shí)候，才將capacity 減半，實(shí)現(xiàn)方式如下：

 
 
 
 
    
  
  
  
  
  1. //從數(shù)組中刪除index位置的元素，返回刪除的元素
    2. 
  
  
  
  
  2.     public E remove(int index){
    3. 
  
  
  
  
  3.         if(index < 0 || index >= size)
    4. 
  
  
  
  
  4.             throw new IllegalArgumentException("remove failed . Index is illegal.");
    5. 
  
  
  
  
  5. 
  
  
  
  
  6.         E ret = data[index];
    7. 
  
  
  
  
  7.         for (int i = index+1 ; i < size; i++)
    8. 
  
  
  
  
  8.                 data[i - 1] = data[i];
    9. 
  
  
  
  
  9. 
  
  
  
  
  10.         size--;
    11. 
  
  
  
  
  11.         // loitering objects != memory leak
    12. 
  
  
  
  
  12.         data[size] = null;//如果一旦使用新的元素，添加新的對象就會覆蓋掉
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.         if(size == data.length / 4 && data.length / 2 != 0)
    15. 
  
  
  
  
  15.             resize(data.length / 2);
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.         return ret;
    18. 
  
  
  
  
  18.     }
    19.

完整代碼：

 
 
 
 
    
  
  
  
  
  1. package com.bj.array;
    2. 
  
  
  
  
  2. 
  
  
  
  
  3. 
  
  
  
  
  4. /**
    5. 
  
  
  
  
  5.  * @program: Data-Structures
    6. 
  
  
  
  
  6.  * @ClassName Array
    7. 
  
  
  
  
  7.  * @description:
    8. 
  
  
  
  
  8.  * @author: lyy
    9. 
  
  
  
  
  9.  * @create: 2019-11-18 22:27
    10. 
  
  
  
  
  10.  * @Version 1.0
    11. 
  
  
  
  
  11.  **/
    12. 
  
  
  
  
  12. public class ArrayPlus {
    13. 
  
  
  
  
  13. 
  
  
  
  
  14.     private E[] data;
    15. 
  
  
  
  
  15.     private int size;
    16. 
  
  
  
  
  16. 
  
  
  
  
  17.     //構(gòu)造函數(shù)，傳入數(shù)組的容量capacity 構(gòu)造array
    18. 
  
  
  
  
  18.     public ArrayPlus(int capacity){
    19. 
  
  
  
  
  19.         data = (E[])new Object[capacity];
    20. 
  
  
  
  
  20.         size = 0;
    21. 
  
  
  
  
  21.     }
    22. 
  
  
  
  
  22.     //無參數(shù)的構(gòu)造函數(shù)，傳入數(shù)組的容量capacity=10
    23. 
  
  
  
  
  23.     public ArrayPlus(){
    24. 
  
  
  
  
  24.         this(10);
    25. 
  
  
  
  
  25.     }
    26. 
  
  
  
  
  26. 
  
  
  
  
  27.     //獲取元素中的個(gè)數(shù)
    28. 
  
  
  
  
  28.     public int getSize(){
    29. 
  
  
  
  
  29.         return size;
    30. 
  
  
  
  
  30.     }
    31. 
  
  
  
  
  31. 
  
  
  
  
  32.     //獲取數(shù)組的容量
    33. 
  
  
  
  
  33.     public int getCapacity(){
    34. 
  
  
  
  
  34.         return data.length;
    35. 
  
  
  
  
  35.     }
    36. 
  
  
  
  
  36. 
  
  
  
  
  37.     //返回?cái)?shù)組是否為空
    38. 
  
  
  
  
  38.     public boolean isEmpty(){
    39. 
  
  
  
  
  39.         return size == 0;
    40. 
  
  
  
  
  40.     }
    41. 
  
  
  
  
  41. 
  
  
  
  
  42.     //在所有元素后添加一個(gè)新元素
    43. 
  
  
  
  
  43.     public void addLast(E e){
    44. 
  
  
  
  
  44.         add(size,e);
    45. 
  
  
  
  
  45.     }
    46. 
  
  
  
  
  46. 
  
  
  
  
  47.     //想所有元素前添加一個(gè)新元素
    48. 
  
  
  
  
  48.     public void addFirst(E e){
    49. 
  
  
  
  
  49.         add(0,e);
    50. 
  
  
  
  
  50.     }
    51. 
  
  
  
  
  51. 
  
  
  
  
  52.     //在第Index個(gè)位置插入一個(gè)新元素e
    53. 
  
  
  
  
  53.     public void add(int index,E e){
    54. 
  
  
  
  
  54. 
  
  
  
  
  55.         if(index < 0 || index > size)
    56. 
  
  
  
  
  56.             throw new IllegalArgumentException("Add failed . Require index < 0 || index > size.");
    57. 
  
  
  
  
  57. 
  
  
  
  
  58.         if(size == data.length)
    59. 
  
  
  
  
  59.             resize(2 * data.length);
    60. 
  
  
  
  
  60. 
  
  
  
  
  61. 
  
  
  
  
  62.         for (int i = size - 1; i >= index ; i--)
    63. 
  
  
  
  
  63.             data[i+1] = data[i];
    64. 
  
  
  
  
  64. 
  
  
  
  
  65.         data[index]  = e;
    66. 
  
  
  
  
  66.         size++;
    67. 
  
  
  
  
  67.     }
    68. 
  
  
  
  
  68. 
  
  
  
  
  69. 
  
  
  
  
  70. 
  
  
  
  
  71.     //獲取index索引位置的元素
    72. 
  
  
  
  
  72.    public E get(int index){
    73. 
  
  
  
  
  73.         if(index < 0 || index >= size)
    74. 
  
  
  
  
  74.             throw new IllegalArgumentException("Get failed . Index is illegal.");
    75. 
  
  
  
  
  75. 
  
  
  
  
  76.         return data[index];
    77. 
  
  
  
  
  77.     }
    78. 
  
  
  
  
  78. 
  
  
  
  
  79.     //修改index索引位置的元素為e
    80. 
  
  
  
  
  80.     public void set(int index,E e){
    81. 
  
  
  
  
  81.         if(index < 0 || index >= size)
    82. 
  
  
  
  
  82.             throw new IllegalArgumentException("Set failed . Index is illegal.");
    83. 
  
  
  
  
  83. 
  
  
  
  
  84.          data[index] = e;
    85. 
  
  
  
  
  85.     }
    86. 
  
  
  
  
  86. 
  
  
  
  
  87.     //查找數(shù)組中是否有元素e
    88. 
  
  
  
  
  88.     public boolean contains(E e){
    89. 
  
  
  
  
  89.         for (int i = 0; i < size; i++) {
    90. 
  
  
  
  
  90.             if(data[i].equals(e))
    91. 
  
  
  
  
  91.                 return true;
    92. 
  
  
  
  
  92.         }
    93. 
  
  
  
  
  93.         return false;
    94. 
  
  
  
  
  94.     }
    95. 
  
  
  
  
  95. 
  
  
  
  
  96.     //查找數(shù)組中元素e所在的索引，如果不存在元素e，則返回-1
    97. 
  
  
  
  
  97.     public int find(E e){
    98. 
  
  
  
  
  98.         for (int i = 0; i < size; i++) {
    99. 
  
  
  
  
  99.             if(data[i].equals(e))
    100. 
  
  
  
  
  100.                 return i;
    101. 
  
  
  
  
  101.         }
    102. 
  
  
  
  
  102.         return -1;
    103. 
  
  
  
  
  103.     }
    104. 
  
  
  
  
  104. 
  
  
  
  
  105.     //從數(shù)組中刪除index位置的元素，返回刪除的元素
    106. 
  
  
  
  
  106.     public E remove(int index){
    107. 
  
  
  
  
  107.         if(index < 0 || index >= size)
    108. 
  
  
  
  
  108.             throw new IllegalArgumentException("remove failed . Index is illegal.");
    109. 
  
  
  
  
  109. 
  
  
  
  
  110.         E ret = data[index];
    111. 
  
  
  
  
  111.         for (int i = index+1 ; i < size; i++)
    112. 
  
  
  
  
  112.                 data[i - 1] = data[i];
    113. 
  
  
  
  
  113. 
  
  
  
  
  114.         size--;
    115. 
  
  
  
  
  115.         // loitering objects != memory leak
    116. 
  
  
  
  
  116.         data[size] = null;//如果一旦使用新的元素，添加新的對象就會覆蓋掉
    117. 
  
  
  
  
  117. 
  
  
  
  
  118.         if(size == data.length / 4 && data.length / 2 != 0)
    119. 
  
  
  
  
  119.             resize(data.length / 2);
    120. 
  
  
  
  
  120. 
  
  
  
  
  121.         return ret;
    122. 
  
  
  
  
  122.     }
    123. 
  
  
  
  
  123. 
  
  
  
  
  124.     //從數(shù)組中刪除第一個(gè)位置的元素，返回刪除的元素
    125. 
  
  
  
  
  125.     public E removeFirst(){
    126. 
  
  
  
  
  126.         return remove(0);
    127. 
  
  
  
  
  127.     }
    128. 
  
  
  
  
  128. 
  
  
  
  
  129.     //從數(shù)組中刪除最后一個(gè)位置的元素，返回刪除的元素
    130. 
  
  
  
  
  130.     public E removeLast(){
    131. 
  
  
  
  
  131.         return remove(size-1);
    132. 
  
  
  
  
  132.     }
    133. 
  
  
  
  
  133. 
  
  
  
  
  134.     //從數(shù)組中刪除元素e
    135. 
  
  
  
  
  135.     //思考？如果返回是否刪除成功 2、如果存在重復(fù)數(shù)據(jù)，如何刪除多個(gè)
    136. 
  
  
  
  
  136.     public void removeElement(E e){
    137. 
  
  
  
  
  137.         int index = find(e);
    138. 
  
  
  
  
  138.         if(index != -1)
    139. 
  
  
  
  
  139.             remove(index);
    140. 
  
  
  
  
  140. 
  
  
  
  
  141.     }
    142. 
  
  
  
  
  142. 
  
  
  
  
  143.     @Override
    144. 
  
  
  
  
  144.     public String toString(){
    145. 
  
  
  
  
  145.         StringBuffer res = new StringBuffer();
    146. 
  
  
  
  
  146.         res.append(String.format("Array：Size = %d，capacity = %d\n",size,data.length));
    147. 
  
  
  
  
  147.         res.append("[");
    148. 
  
  
  
  
  148.         for (int i = 0; i < size; i++) {
    149. 
  
  
  
  
  149.             res.append(data[i]);
    150. 
  
  
  
  
  150.             if(i != size - 1)
    151. 
  
  
  
  
  151.                 res.append("，");
    152. 
  
  
  
  
  152.         }
    153. 
  
  
  
  
  153.         res.append("]");
    154. 
  
  
  
  
  154.         return res.toString();
    155. 
  
  
  
  
  155.     }
    156. 
  
  
  
  
  156. 
  
  
  
  
  157.     private void resize(int newCapacity) {
    158. 
  
  
  
  
  158.         E[] newData = (E[])new Object[newCapacity];
    159. 
  
  
  
  
  159.         for (int i = 0; i < size; i++)
    160. 
  
  
  
  
  160.             newData[i] = data[i];
    161. 
  
  
  
  
  161.         data = newData;
    162. 
  
  
  
  
  162.     }
    163. 
  
  
  
  
  163. 
  
  
  
  
  164. }
    165.

 有時(shí)候更"懶"，會讓我們的程序更方便點(diǎn)，我是牧小農(nóng)，大家加油!


分享題目：數(shù)據(jù)結(jié)構(gòu)—動態(tài)數(shù)組和時(shí)間復(fù)雜度分析
網(wǎng)站鏈接：http://www.dlmjj.cn/article/dhsccec.html