在这种情况下，BIG O 分析是什么？

Question

我想知道在这种情况下 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))

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

Answer 2

为了正确理解复杂性，我们需要正确理解无穷大的概念。

首先，有一个实际无穷大的概念，它要么无限大，要么无限小。

其次，有一个聚类点的概念，即一个阈值，超过该阈值我们不关心实际边界，因为它太大或太小。

例如，如果你必须步行 30 000 英里，那么它并不是真正的无穷大，但它超出了你仍然关心大小的阈值。

所以，当人们分析函数时，他们要么任意地要么有充分理由选择一个误差限度，即你正在接近的值与实际值之间的最大距离，即你允许的最大误差。这指定了您的聚类点所在的位置。

现在，复杂度是决定算法遵循模式的函数，随着输入大小的增加，其步骤数接近无穷大。

你的情况是你的输入大小保证总是很小，所以当它变得太慢时你永远不会到达聚类点。但是，函数的复杂性并不取决于当输入大小几乎为零时它的执行方式，而是取决于它到达集群点的速度，您不再等待它被执行。