运行时间复杂度分析

huangapple
go评论103阅读模式
英文:

Analysis of run time complexity

问题

  1.     /**
  2.     *mostOften方法
  3.     *@param array 数组[]，整数n
  4.     */
  5.     
  6.     static int mostOften(int array[], int n){
  7.      
  8.         // 将数组升序排序
  9.         Arrays.sort(array);
  10.         
  11.         // 计算数组中的最大出现次数
  12.         int maxO = 1;
  13.         
  14.         // 跟踪数组中的整数
  15.         int result = array[0];
  16.         
  17.         // 计数变量
  18.         int count = 1;
  19.         
  20.         /**
  21.         * 循环按线性方式遍历数组，并比较索引i处和索引i-1处的元素。
  22.         * 根据可能的每种情况递增count和maxO。
  23.         */
  24.         for(int i = 1; i < n; i++){ 
  25.             
  26.             // 如果整数相同，则递增count。
  27.             if (array[i] == array[i - 1]){ 
  28.                 count++;  
  29.             }//关闭if语句
  30.             
  31.             // 否则，如果整数不同
  32.             else{
  33.              
  34.                 // 如果count大于maxO，则该整数具有更高的出现次数
  35.                 if (count > maxO){ 
  36.                 
  37.                     // count现在变为maxO
  38.                     maxO = count; 
  39.                    
  40.                     // 用具有最高出现次数的整数替换result。
  41.                     result = array[i - 1]; 
  42.                 }//关闭if语句
  43.                 
  44.                 // 将count重置为1。
  45.                 count = 1; 
  46.             }//关闭else语句
  47.         }//关闭for循环
  48.         
  49.         //@返回int数据类型
  50.         return result;
  51.     }//关闭mostOften方法
英文:

I need some help below I have some code I created for an assignment. I am having a hard time figuring out the time complexity of this algorithm. I looked at it and believe the O-notation is 0(n) and the function is F(n)= 4 + 2n. But I think that is incorrect.

  1. /**
  2. *mostOften method 
  3. *@param receives Array[] , int
  4. */
  6.  static int mostOften(int array[] , int n){
  7.  
  8.  //Array to be sorted in ascending order
  9.  Arrays.sort(array);
  10.  
  11.  //counts number of max occurrences in the array
  12.  int maxO = 1;
  13.  
  14.  //Keeps track of the integer at Array[i].
  15.  int result = array[0];
  16.  
  17.  //variable to count occurrences
  18.  int count = 1;
  19.  
  20.  /**
  21.  *loop passes through array in linear motion and compares index at i and index at
  22.  * i - 1. For every possible outcome count and maxO are incremented accordingly.
  23.  */
  24.   for(int i = 1 ; i &lt; n ; i++){ 
  25.   
  26.         //If integers are the same increment count.
  27. 			if (array[i] == array[i - 1]){ 
  28. 				count++;  
  29.             }//close if statement
  30.             
  31.         // else if integers are not the same 
  32.          else{
  33.          
  34. 			   //if count is larger thatn maxO that integer is the highers occurrence
  35. 				if (count &gt; maxO){ 
  36.             
  37. 				   //count is now maxO
  38. 					maxO = count; 
  39.                
  40.                //replaces result with integers with highest occurrence.
  41. 					result = array[i - 1]; 
  42. 				}//close if statement
  43.              
  44.             //reset count to 1.
  45. 				count = 1; 
  46.             
  47. 			}//close else statement
  48.          
  49.   }//close for loop
  50.   
  51.       //@returns int data type
  52. 		return result;
  53.   
  54.  }//close mostOften method

答案1

得分: 2

只想指出Arrays.sort本身的时间复杂度是O(n logn)。
如果我们忽略这一点，循环所需时间是线性的。

英文:

Just wanted to point out that Arrays.sort itself is O(n logn).
If we ignore that, the loop takes linear time.

huangapple
  • 本文由 发表于 2020年9月9日 08:50:31
  • 转载请务必保留本文链接：https://go.coder-hub.com/63803302.html
  • java
  • time-complexity
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定