大O符号 - 数量级

Question

3

我目前正在研究二次、三次和指数算法之间的主要量化差异。

我不理解“量化”是什么意思以及这个问题具体在问什么。我尝试搜索相关信息，但没有找到有帮助的信息。

谢谢。

- user1028145

1

@FelicePollano：cstheory 是针对研究级别的计算机科学问题，cs.stackexchange.com 可能更适合这个问题，但我认为 stackoverflow 对于这个水平的问题也是可以的。 - Peter Alexander

@HåvardGeithus 好的，我现在明白了！只有最后一件事我不明白。例如，当N = 2时，n^2和2^n都给出相同的答案，但是对于n = 8，它们是不同的。你如何计算一个值的2^n？ - user1028145

1

n^2 = n * n，但是2^n表示222...以此类推，重复n次。如果你手边没有计算器，可以在谷歌上输入例如2^10来计算。 - Håvard Geithus

@PeterAlexander 同意，抱歉我指错了网站，我也会投票给 CS。 - Felice Pollano

不客气。顺便说一下，http://www.khanacademy.org/ 是一个提高数学直觉的好资源 :) 至少这是我的经验（那里还涵盖了许多其他有趣的主题）。 - Håvard Geithus

显示剩余6条评论

2个回答

2

量化差异指的是数量上的差异--也就是说，这些不同种类的算法之间的大小差异是什么？最好给出数值示例，例如展示二次、三次和指数算法在某些示例问题规模下的运行时间。

- Peter Alexander

例如，如果我要使用值n = 1、2、4、10和20。我该如何从这些值计算问题的大小？ - user1028145

@user1028145：n 是问题的规模。对于二次问题，运行时间为 n * n，对于三次问题，运行时间为 n * n * n，对于指数问题，运行时间为 e ^ n。 - Peter Alexander

它可以是任何数字k，而不仅仅是通常表示约为2.71828的e。 - Håvard Geithus

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Håvard Geithus · Accepted Answer

当你使用大O符号来估算算法的计算复杂度时，目标是为了提供一个定性的洞察，以说明当N变得很大时，如何改变算法性能。如果你消除任何随着N变得很大会对总和贡献不重要的项，并且消除任何常数因子，那么你可以说你留下了主要的定量差异。