需要有关大 O 表示法的信息

Question

对你来说是一个随机的问题。如果你有一个方法必须检查数组中的每个位置，是否可以说这个方法有O（n）的符号？

我

不确定我的答案是否正确的原因是，据我所知，O（n） 与数组中保存的项目数有关，而我的假设是基于数组的实际大小？

Answer 1

如果你的算法必须查看数组中的每个项目，则该算法是 O（n）。if 数组是否已满并不重要，因为您可以灵活地定义 n。它可以是数组的大小或数组中非空元素的数量。如果您的算法必须查找空数组插槽以查看它们是否为空，请使用大小。（如果这是一个真正的性能问题，则可能需要不同的数据结构。

对于一个非常人为的例子，如果处理每个非空数组元素需要一个小时，但检查空值需要一纳秒，那么你应该将n定义为实际存在的元素数，因为这将决定算法如何扩展。