它是更大的线性时间复杂度吗？

Question

谁能告诉我下面代码的最差时间复杂度是多少？是线性的还是更大的？

void fun(int[] nums){
{
  int min = min(nums);
  int max = max(nums);
  for(int i= min; i<=max;i++){
    print(i); //constant complexity for print
  }
}
int min(int[] nums);//return min in nums in linear time
int max(int[] nums);//return max in nums in linear time

在哪里 0 <= nums.length <= 10^4 和 -10^9 <= nums[i] <= 10^9

我能说这段代码的时间复杂度是 O(Max(nums[i]) - Min(nums[i])) 我能说吗，这是线性时间复杂度?

Answer 1

如果数字的范围是常数（即-10^9 <= nums[i] <= 10^9）那么

for(int i= min; i<=max;i++){
  print(i); //constant complexity for print
}

在 O(1) 中，即常量，因为你知道，它最多迭代 2 * 10^9 个数字，而不管 [=] 中有多少个数字14=]数组。因此它不依赖于输入数组的大小。

考虑以下输入数组

nums = [-10^9, 10^9];  //size 2
nums = [-10^9, -10^9 + 1, -10^9 + 2, ..., 10^9 - 2, 10^9 - 1, 10^9]  //size 2 * 10^9 + 1

对于 min 和 max 将分别具有相同的值 -10^9 和 10^9。因此，您的循环将迭代从 -10^9 到 10^9 的所有数字。即使原始数组中有 10^100000 个数字，for 循环也最多从 -10^9 迭代到 10^9.

而你说 min() 和 max() 在 O(n) 中，因此你的整体算法也会在 O 中(n)。但是，如果您随后考虑到数组的给定最大长度 (10^4) 比您的数字限制小很多，您甚至可以忽略调用 min 和 max

至于你的评论

For ex. array =[1,200,2,6,4,100]. In this case we can find min and max in linear time(O(n) where n is length of array). Now, my for loop complexity is O(200) or O(n^3) which is much more than length of array. Can I still say its linear complexity

数组的大小和数组中的值是完全独立的。因此，您不能用 n 来表达 for 循环的复杂性（如上所述）。如果您真的还想考虑数字的范围，则必须以某种方式表达它 O(n + r) where n是数组的大小，r是数字的范围。

Answer 2

由于复杂度与数据范围 R = max - min 呈线性关系，因此我将其称为 伪线性 复杂度。 O(N + R).

此维基百科条目中有详细说明：Pseudo-polynomial time

如本文引言所述：

In computational complexity theory, a numeric algorithm runs in pseudo-polynomial time if its running time is a polynomial in the numeric value of the input (the largest integer present in the input)—but not necessarily in the length of the input (the number of bits required to represent it), which is the case for polynomial time algorithms.

通常，在分析给定算法的复杂性时，我们不会对特定目标语言的固有范围限制做出任何具体假设，当然除非在问题中特别提到这一点。

它是更大的线性时间复杂度吗？

Is it linear Time Complexity of Bigger?

iteration

algorithm

time-complexity