我正在研究数值分析，我可以读到算法的复杂度为“大约 n^2/2”。
我知道复杂性与写/读/乘/求和操作有关，但我不明白为什么“大约”而不是“精确”。
问问题
113 次
1 回答
1
在算法分析中，通常只通过显性增长项来描述算法的增长率。例如，如果算法的实际运行时间为 n 2 /2 + 13n + 1，那么随着 n 变大（例如，n > 50），几乎所有运行时间都由 n 2 /2 项解释，并且非常其他两个术语贡献很小。
在大部分计算机科学中，算法是使用大 O 表示法来描述的，它完全丢弃了除主要增长项之外的所有内容，甚至丢弃了所有常数因子。在数值计算中，通常只是保持主要增长项及其常数因子，因为对于大输入，该项几乎决定了所有运行时间。不过，常数因子对于比较不同的算法仍然很有用。
简而言之 - 人们可以获得精确的分析，但对于大型问题来说它不是很有用。占主导地位的增长术语真的很重要。
希望这可以帮助！
于 2013-02-03T22:08:14.877 回答