java - O(n log n) 时间复杂度算法？

Question

我创建这个算法是为了找到 3 个数字之间的最佳交易。它会执行该程序并找到出售、购买股票并从股票中获利的最佳日期。我需要解释所使用的算法以及时间复杂度如何为 O(n log n)，但我很难确定这一点。我希望有人可以解释 O(n log n) 并将其与我的方法联系起来。

这是我的方法:

public static Trade bestTrade(int[] a) 
   {
      int lowest = a[0];
      int lowestIndex = 0;
      int highest = a[a.length - 1];
      int highestIndex = a.length - 1;
      int profit = 0;

      for(int i = 1; i < a.length; i++) 
      {
         if (a[i] < lowest && i < highestIndex) 
         {
            lowest = a[i];
            lowestIndex = i;
         }  
      }

      for(int i = a.length - 2; i >= 0; i--) 
      {
         if (a[i] > highest && i > lowestIndex) 
         {  
            highest = a[i];   
            highestIndex = i;
         }  
      }

      for(int i = 1; i < a.length; i++) 
      {
         if (a[i] < lowest && i < highestIndex) 
         {   
            lowest = a[i];   
            lowestIndex = i;
         }  
      }

      if (highestIndex > lowestIndex) 
      {
         profit = highest - lowest;
         return new Trade(lowestIndex, highestIndex, profit);
      }

      return new Trade(lowestIndex, highestIndex, profit);
   }

}

Answer 1

该函数的复杂度为 O(n)，优于 O(n log n) 。 一般来说，您只需查看循环，因为没有嵌套循环，并且只有遍历 a 的所有元素的循环。该函数被视为 n。