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。