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

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]))我可以说这是线性时间复杂度吗？

标签： algorithmiterationtime-complexity

Answer 1

由于复杂度相对于R = max - min数据范围是线性的，我将其称为伪线性复杂度。O（N + R）。

这在此 Wikipedia 条目中有详细说明：伪多项式时间

正如这篇文章的介绍所提到的：

在计算复杂性理论中，如果数值算法的运行时间是输入数值（输入中存在的最大整数）的多项式，则数值算法在伪多项式时间内运行 - 但不一定是输入的长度（数字表示它所需的位数），这是多项式时间算法的情况。

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