合併2個數組，保持排序，並找到效率

Question

所以，我發現一個有趣的問題，你給了2個排序的數組，你的任務是將它們組合成一個新的數組，並保持排序。另外，找到你的程序的效率。我得到了我的代碼工作，但我不確定效率..我認爲這是O（n），因爲我使用while循環遍歷數組的每個元素。有小費嗎？有沒有辦法讓這更高效？ O（n）是否正確？這裏是代碼：

class mergesorted{ 
    static void Main(string[] args){ 
     int[] x = { 1, 3, 7}; 
     int[] y = { 2, 4, 5, 6, 15}; 
     int[] retrieval = answer(x, y); 

     for (int i = 0; i < retrieval.Length; i++){ 
      Console.WriteLine(retrieval[i]);     
     } 
     Console.ReadLine(); 
    } 

    public static int[] answer(int[] x, int[] y) 
    { 
     int[] a = x; 
     int[] b = y; 
     int abc = 0; //counter for a 
     int abc2 = 0; //counter for b 
     int i = 0; //counter for index of new array 
     Boolean flagA = true; //if flag changed, array is exhaused 
     Boolean flagB = true; 
     int[] newarray = new int[a.Length+b.Length]; //so size is 7 

     while (abc < a.Length && abc2 < b.Length){ 
      if (a[abc] < b[abc2]){ 
       newarray[i] = a[abc]; 
       abc++; 
      } 
      else{ 
       newarray[i] = b[abc2]; 
       abc2++; 
      } 

      if (abc >= a.Length){ 
       flagA = true; 
       flagB = false; 
      } 

      else if (abc2 >= b.Length){ 
       flagA = false; 
       flagB = true; 
      } 
      i++; 
     } 

     if (flagA == false){ 
      while (abc < a.Length){ 
       newarray[i] = a[abc]; 
       abc++; 
       i++; 
      } 
     } 
     else if (flagB == false){ 
      while (abc2 < b.Length){ 
       newarray[i] = b[abc2]; 
       abc2++; 
       i++; 
      } 
     } 
     return (newarray); 
    } 
} 

Answer 1

您有很多冗餘測試。但是你的算法是O（N），因爲它觸及每個元素一次。由於構建最終的數組是O（N），所以你不能做得比這更好（在一般情況下）。

在特殊情況下，一個數組比另一個數組大得多，並且您有一個O（1）插入（或移動）操作，您可以使算法爲O（A log B），其中A是數字的較小列表中的條目數量，B是較大列表中的條目數量。例如，如果一個數組有1,000,000個對象，而另一個數組只有2個，則可以使用二分查找來找出在1,000,000個對象列表中的哪個位置移動另一個列表中的每個對象。如果這兩個列表的大小相同，這並沒有幫助。