javao（nlogn）时间复杂度算法？

Question

我创建这个算法是为了找到3个数字之间的最佳交易。它通过该计划，找到出售、购买和从股票中获利的最佳时机。我需要解释使用的算法，以及时间复杂度是如何为O（n logn），但我很难确定这一点。我希望有人能解释O（n logn）并将其与我的方法联系起来

以下是我的方法：

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（NlogN）

这个链接可能有用， http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html

Answer 2

O（n）

它与a的长度成正比。每次运行for函数时，它都会遍历每天的数据。如果有一种方法，其中进程数增加的幅度大于纯数（嵌套FOR），那么它可以是O（n logn）或O（n^2）。但在这种情况下，很明显这只是n中的O

Answer 3

这个函数是O（n）函数，它优于O（n logn）。 一般来说，你只需要看看循环，因为没有嵌套的循环，只有穿过函数所有元素的循环，函数被认为是n

Answer 4

复杂度是O（n），其中n是数组a的长度

在a上循环3次，所以运行时间大约是3n，所以它的顺序是n:O（n）