英文:
Analysis of run time complexity
问题
/**
*mostOften方法
*@param array 数组[]，整数n
*/
static int mostOften(int array[], int n){
// 将数组升序排序
Arrays.sort(array);
// 计算数组中的最大出现次数
int maxO = 1;
// 跟踪数组中的整数
int result = array[0];
// 计数变量
int count = 1;
/**
* 循环按线性方式遍历数组，并比较索引i处和索引i-1处的元素。
* 根据可能的每种情况递增count和maxO。
*/
for(int i = 1; i < n; i++){
// 如果整数相同，则递增count。
if (array[i] == array[i - 1]){
count++;
}//关闭if语句
// 否则，如果整数不同
else{
// 如果count大于maxO，则该整数具有更高的出现次数
if (count > maxO){
// count现在变为maxO
maxO = count;
// 用具有最高出现次数的整数替换result。
result = array[i - 1];
}//关闭if语句
// 将count重置为1。
count = 1;
}//关闭else语句
}//关闭for循环
//@返回int数据类型
return result;
}//关闭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.
/**
*mostOften method
*@param receives Array[] , int
*/
static int mostOften(int array[] , int n){
//Array to be sorted in ascending order
Arrays.sort(array);
//counts number of max occurrences in the array
int maxO = 1;
//Keeps track of the integer at Array[i].
int result = array[0];
//variable to count occurrences
int count = 1;
/**
*loop passes through array in linear motion and compares index at i and index at
* i - 1. For every possible outcome count and maxO are incremented accordingly.
*/
for(int i = 1 ; i < n ; i++){
//If integers are the same increment count.
if (array[i] == array[i - 1]){
count++;
}//close if statement
// else if integers are not the same
else{
//if count is larger thatn maxO that integer is the highers occurrence
if (count > maxO){
//count is now maxO
maxO = count;
//replaces result with integers with highest occurrence.
result = array[i - 1];
}//close if statement
//reset count to 1.
count = 1;
}//close else statement
}//close for loop
//@returns int data type
return result;
}//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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论