-4

我忘记了如何计算算法的时间复杂度。我不是在寻找一本书或 30 页的博客来刷新这些知识。采用以下算法，请您纠正我计算时间复杂度的方式。谢谢

线性搜索

bool SeqSearch(int[] arr, int sValue) {
    for (int index = 0; index < arr.Length-1; index++)
    if (arr[index] == sValue)
        return true;
    return false;
}

使用的步骤和逻辑

  1. 循环遍历所有元素 -N
  2. 每个指数的比较 -1或者是N
  3. 返回真或假 -1

最后

我忘了我们是把它们加起来还是相乘？我以为我们必须添加， N+N+1所以这一定是一个大哦！的 N。O(N)

问题

  1. 我是乘以每个步骤所花费的时间还是将它们相加
  2. 对于比较，无法确定何时结束。那么需要多少时间（我假设 1 因为它可以在第一个索引处找到，N 否则作为最后一个索引）
  3. 分配和回报是恒定的时间 1 ？

注意：请不要让我访问网站。SO 会持续很长时间，有相同/相似问题的人肯定会发现这篇文章的答案很有用。我无法相信其他网站何时会被关闭等。我也不在乎效率、时间复杂性，而是用于查找它的过程/步骤。

资源

http://faculty.simpson.edu/lydia.sinapova/www/cmsc250/LN250_Weiss/L03-BigOh.pdf

我只是想把这个链接放到 pdf 中，它清楚地解释了如何解释什么陈述以及何时解释。就像我想要的一样。

4

1 回答 1

5

考虑原始操作（内存访问和算术/逻辑操作）。

给定输入的大小N（arr.Length在您的情况下），为您的算法计算它们。

然后查看操作总数与 的关系N，无论它只是某个常数或多项式N（例如N3）还是 的对数N或指数N或其他东西。

如果结果类似于N+1 或 2* N，您应该忽略小常数，因为您主要关心N大时会发生什么以及整体行为。

这就是基础。

这是最坏情况下的近似时间复杂度（当sValue不在时arr[]）：

int index = 0;是 1

index < arr.Length-1;为 1（但可能高达 10 次），重复arr.Length次数

index++为 1（但可能最多为 3），重复arr.Length次数

if (arr[index] == sValue)为 1（但可能高达 10 次），重复arr.Length次数

return value;是 1

所以你有类似 1 + 1 * arr.Length+ 1 * arr.Length+ 1 * arr.Length= 1 + 3 * arr.Length+ 1 的东西。你把它简化为arr.Length，因此 O( N)。

平均而言，您将只有arr.Length/ 2 次迭代。因此，平均而言，您有 1 + 1 * arr.Length/ 2 + 1 * arr.Length/ 2 + 1 * arr.Length/ 2 + 1 = 2 + 1.5 * arr.Length。再次，O( N)。

但你真的应该阅读这些东西。

于 2012-06-23T05:55:00.783 回答