线性时间复杂度更大吗？
有人能告诉我下面代码最糟糕的时间复杂度是什么吗？是线性的还是更大的？
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 <= numsi <= 10^9
我是否可以说，这段代码的时间复杂度是O(Max(numsi) - Min(numsi))，这是线性时间复杂度？
回答 2
Stack Overflow用户
发布于 2021-03-19 08:31:56
如果数的范围是常数(即-10^9 <= nums[i] <= 10^9)，那么
for(int i= min; i<=max;i++){
print(i); //constant complexity for print
}在O(1)中，即常量，因为您知道，它迭代最多的2 * 10^9数，而不管nums[]数组中有多少个数字。因此，它不依赖于输入数组的大小。
考虑以下输入数组
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。
至于你的评论
为了前夫。数组=1 200、2 6、4 100。在这种情况下，我们可以在线性时间(O(N)，其中n是数组的长度)求出最小和最大。现在，我的for循环复杂度是O(200)或O(n^3)，这大大超过了数组的长度。我还可以说它的线性复杂性吗？
数组的大小和数组中的值是完全独立的。因此，您不能用for (如前所述)表示n循环的复杂性。如果你真的想要考虑数字的范围，你必须用O(n + r)来表示，其中n是数组的大小，r是数字的范围。
Stack Overflow用户
发布于 2021-03-19 09:39:23
由于复杂度相对于数据的范围R = max - min是线性的，所以我称之为伪线性复杂性。O(N + R)。
这在维基百科的条目中有详细的内容：伪多项式时间
如本条导言所述：
在计算复杂性理论中，如果一个数值算法的运行时间是输入的数值(输入中的最大整数)的多项式，而不一定是输入的长度(表示它所需的比特数)，则一个数值算法运行在伪多项式时间中，这就是多项式时间算法的情况。
通常，在分析给定算法的复杂性时，我们不会对特定目标语言的固有范围限制做出任何具体假设，当然，如果在问题中特别提到这一点，则例外。
https://stackoverflow.com/questions/66704389
复制相似问题
腾讯云开发者
