英文:
Algorithm that finds the maximum product - Analysis
问题
我有这段代码，它在数组中计算出使用3个数字可以找到的最大乘积：
public static int findMaxProduct(int[] arr) {
int i=0, j=1, f=2;
int largest = arr[i]*arr[j]*arr[f];
for(;i<arr.length;) {
if(largest<arr[i]*arr[j]*arr[f])
largest = arr[i]*arr[j]*arr[f];
if(i==arr.length-3)
return largest;
if(f==arr.length-1 && j == arr.length - 2) {
i++;
j=i+1;
}
if( f==arr.length-1 && j != arr.length-2)
f = j+1;
if(f<arr.length-1)
f++;
if(f==arr.length -1 && j < arr.length -2)
j++;
}
return 0;
}
现在，我不确定它的复杂度是什么，因为我们只有在满足条件时才会增加“i”，而且我们不知道何时会执行“i++”。如果您能帮助我找出复杂度，我将不胜感激！（时间）
英文:
I have this code which is calculating the largest product you can find using 3 numbers in an array:
public static int findMaxProduct(int[] arr) {
int i=0, j=1, f=2;
int largest = arr[i]*arr[j]*arr[f];
for(;i<arr.length;) {
if(largest<arr[i]*arr[j]*arr[f])
largest = arr[i]*arr[j]*arr[f];
if(i==arr.length-3)
return largest;
if(f==arr.length-1 && j == arr.length - 2) {
i++;
j=i+1;
}
if( f==arr.length-1 && j != arr.length-2)
f = j+1;
if(f<arr.length-1)
f++;
if(f==arr.length -1 && j < arr.length -2)
j++;
}
return 0;
}
Now, I am not sure of what complexity it is, as we increment i if only a condition is met, and we don't know where it's going to execute i++ . I would appreciate if you help me find the complexity! (Time)
答案1
得分: 2
你测试所有的三元组。大约有 n^3 个。因此复杂度是 O(n^3)。
英文:
You test all the triplets. There are about n^3 of them. Therefore the complexity is O(n^3).
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论