算法寻找最大乘积 – 分析

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

Algorithm that finds the maximum product - Analysis

问题

  1. 我有这段代码，它在数组中计算出使用3个数字可以找到的最大乘积：
  3.     public static int findMaxProduct(int[] arr) {
  5.     		int i=0, j=1, f=2;
  6.     		
  7.     		int largest = arr[i]*arr[j]*arr[f];
  8.     		for(;i<arr.length;) {
  9.     			if(largest<arr[i]*arr[j]*arr[f])
  10.     				largest = arr[i]*arr[j]*arr[f];
  11.     
  12.     			if(i==arr.length-3)
  13.     				return largest;
  14.     			
  15.     			if(f==arr.length-1 && j == arr.length - 2) {
  16.     				i++;
  17.     				j=i+1;
  18.     			}
  19.     			if( f==arr.length-1 && j != arr.length-2) 
  20.     				f = j+1;
  21.     			
  22.     			if(f<arr.length-1)
  23.     				f++;
  24.     			if(f==arr.length -1 && j < arr.length -2)
  25.     				j++;
  26.     				
  27.     			
  28.     			
  29.     			
  30.     		}
  31.     		return 0;
  32.     	}
  34. 现在，我不确定它的复杂度是什么，因为我们只有在满足条件时才会增加“i”，而且我们不知道何时会执行“i++”。如果您能帮助我找出复杂度，我将不胜感激！（时间）
英文:

I have this code which is calculating the largest product you can find using 3 numbers in an array:

  1. public static int findMaxProduct(int[] arr) {
  3. 		int i=0, j=1, f=2;
  4. 		
  5. 		int largest = arr[i]*arr[j]*arr[f];
  6. 		for(;i&lt;arr.length;) {
  7. 			if(largest&lt;arr[i]*arr[j]*arr[f])
  8. 				largest = arr[i]*arr[j]*arr[f];
  10. 			if(i==arr.length-3)
  11. 				return largest;
  12. 			
  13. 			if(f==arr.length-1 &amp;&amp; j == arr.length - 2) {
  14. 				i++;
  15. 				j=i+1;
  16. 			}
  17. 			if( f==arr.length-1 &amp;&amp; j != arr.length-2) 
  18. 				f = j+1;
  19. 			
  20. 			if(f&lt;arr.length-1)
  21. 				f++;
  22. 			if(f==arr.length -1 &amp;&amp; j &lt; arr.length -2)
  23. 				j++;
  24. 				
  25. 			
  26. 			
  27. 			
  28. 		}
  29. 		return 0;
  30. 	}

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).

huangapple
  • 本文由 发表于 2020年5月4日 04:55:53
  • 转载请务必保留本文链接：https://go.coder-hub.com/61581492.html
  • algorithm
  • big-o
  • java
  • time-complexity
匿名

发表评论

匿名网友

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

确定