提问人：Simply Alice 提问时间：10/24/2023 最后编辑：mplungjanSimply Alice 更新时间：10/27/2023 访问量：92
在这种情况下，BIG O 分析是什么？
What would be the BIG O analysis in this case?
问：
我想知道在这种情况下 BIG O 会是什么？我以为是 O（1），因为它有固定的迭代次数（array.length 是固定的）......即使在最坏的情况下（3999），最大迭代仍然是固定的......但我也看到答案可以是 O（n），因为它是与 num 值的线性关系。对于较小的 num 值，while 循环将迭代较少的次数，对于较大的值，它将迭代更多次，但增长率是线性的。
我假设即使迭代是固定的，如果它是线性的，时间复杂度也会是 O（n）？
function convertRomanNumerals(num) {
let romanNumerals = [
[1000, "M"],
[900, "CM"],
[500, "D"],
[400, "CD"],
[100, "C"],
[90, "XC"],
[50, "L"],
[40, "XL"],
[10, "X"],
[5, "V"],
[4, "IV"],
[1, "I"]
];
// 1 =<num =d<3999
// 1990 = M CM XC
// 1666 = M DC LX VI
let result = "";
for (let i = 0; i < romanNumerals.length; i++) {
while (num >= romanNumerals[i][0]) {
result += romanNumerals[i][1];
num -= romanNumerals[i][0];
}
}
return result;
}
console.log(convertRomanNumerals(2023))答：
-1赞
Konrad
10/24/2023
#1
我们可以计算迭代次数并从中获得一些统计数据
function convertRomanNumerals(num) {
let iterations = 0
let romanNumerals = [
[1000, "M"],
[900, "CM"],
[500, "D"],
[400, "CD"],
[100, "C"],
[90, "XC"],
[50, "L"],
[40, "XL"],
[10, "X"],
[5, "V"],
[4, "IV"],
[1, "I"]
];
// 1 =<num =d<3999
// 1990 = M CM XC
// 1666 = M DC LX VI
let result = "";
for (let i = 0; i < romanNumerals.length; i++) {
while (num >= romanNumerals[i][0]) {
result += romanNumerals[i][1];
num -= romanNumerals[i][0];
iterations += 1
}
}
return iterations;
}
const data = []
for (let i = 1; i < 400000; i += 1) {
data.push(convertRomanNumerals(i))
}
console.log(data[0], data[5000], data[20000], data[35000])
const avg1 = data.slice(0, -1).map((a, i) => data[i + 1] - a).reduce((a, b) => a + b) / (data.length - 1)
const avg2 = data.slice(0, -1).map((a, i) => data[i + 1] / a).reduce((a, b) => a + b) / (data.length - 1)
console.log(avg1, avg2)它增加但非常缓慢，所以它肯定不是 O（1）
评论
0赞
Berthur
10/25/2023
num以 3999 为界。
0赞
Lajos Arpad
10/24/2023
#2
为了正确理解复杂性，我们需要正确理解无穷大的概念。
首先，有实际无穷的概念，它要么是无限大的，要么是无限小的，也就是说，你永远不会达到它的极限，无论是大还是小。
其次，有聚类点的概念，即一个阈值，超过这个阈值，我们不关心实际边界，因为它太大或太小。
例如，如果你必须走 30 000 英里，那么它就不是实际的无穷大，但它超出了你仍然关心大小的阈值。
因此，当人们分析函数时，他们要么任意选择，要么有充分的理由选择一个误差限制，即您接近的值与实际值之间的最大距离，即您允许的最大误差。这将指定群集点的位置。
现在，复杂性是确定算法遵循的模式的函数，因为随着输入大小的增加，其步数接近无穷大。
您的情况是，您的输入大小保证始终很小，因此当它变得太慢时，您将永远无法到达集群点。但是，函数的复杂性并不取决于它在输入大小几乎为零时的表现，而是取决于它到达集群点的速度，您不再等待它执行。
0赞
Mo B.
10/27/2023
#3
任何具有有限域的可计算函数都可以用 计算，正如您正确所说。一个更有趣的问题是考虑你为无限域编写的函数，即 where 是无界的。O(1)n
在这种情况下，复杂性并不像您建议的那样。显然，该函数遍历了该行O(n)
result += romanNumerals[i][1];
O(n)times（大约为大），基本上产生一长串 s。字符串连接本身需要线性时间，因此总体时间复杂度是二次的，或 。当然可以重写 中的函数，这将是最佳时间复杂度。n/1000nM+=O(n^2)O(n)
评论
O(n^2)