确定算法的运行时间以比较两个阵列

Question

我想知道如何确定以伪代码编写的算法的运行时间，以便我可以熟悉运行时间。举例来说，你如何知道一个算法的运行时间，它将比较两个数组以确定它们是否不相同？

数组1 = [1,5,3,2,10,12]数组2 = [3,2,1,5,10,12] 因此，这两个数组并不相同，因为它们排序不同。

我的伪代码是：

1）
2）设置的第二指针设置当前指针到第一数目在第一阵列第一数目在第二阵列
3），而（当前指针=““）比较！与
移动当前指针到下一个号码在其它阵列
4相同的位置元件）如果（当前指针==第二指针） 第二指针移动到下一个数

5）否则（输出数组是不一样） end loop

所以我假设第一次我的代码是正确的。我知道第4步只执行一次，因为它只需要1次匹配来显示数组就不一样了。所以第4步只需要一定的时间（1）。我知道第1步和第2步也只执行一次。

到目为为我知道运行时间是3 +？ （？是循环本身的运行时间）

现在我迷失了循环部分。循环是否运行n次（n是数组中的数字？），因为最坏的情况可能是每一个数字都匹配？我是否以正确的方式考虑运行时间？

如果有人可以帮忙，我会感激。

谢谢！

Answer 1

你是对的。运行时间是O（n），其中n是阵列中元素的数量。每次向阵列中添加1个元素时，在最坏的情况下，您必须再次执行循环1次。

Answer 2

你在问什么叫做时间复杂度你的算法。我们讨论使用所谓的Big-O表示法的算法的时间复杂度。

Big-O符号是一种方法，用于说明我们的算法在输入该尺寸的最差情况下，相对于算法输入的大小，采用的大致步骤数。

您的算法运行在O(n)时间（发音为“big-oh of n”或“order n”或有时我们只是说“线性时间”）。

您已经知道步骤1,2和4都以相对于数组大小的恒定步数运行。我们说这些步骤运行在O(1)时间（“恒定时间”）。

因此，让我们考虑第3步：

如果有n个数组中的元素，则步骤3需要做ñ比较在最坏的情况下。所以我们说第3步需要O(n)时间。

由于该算法在步骤3上花费了O(n)时间，并且所有其他步骤都更快，所以我们说您的算法的总时间复杂度为O(n)。

当我们编写O(f)时，其中f是一些函数，我们的意思是该算法对于较大的值在某个常数因子f内运行。

以你的算法为例。对于n的较大值（比如n = 1000），该算法不需要精确的n个步骤。假设一个比较需要5个指令来完成你的算法，在你选择的机器上。 （它可以是任何常数，例如我只选择5）。并且假设步骤1,2,4都采取了一些不变的步骤，这三个步骤共计10条指令。

然后对于n = 1000的算法将采取：

步骤1 + 2 + 4 = 10个指令。步骤3 = 5 * 1000 = 5000条指令。

这是一个总的5010个指令。这是大约5 * n条指令，这是一个常数因子n，这就是为什么我们说它是O(n)。

对于非常大的n，f = 5*n + 10中的10变得越来越微不足道了，因为这样做的原因是，我们只需简单地将函数f is in O(n)减少到f is within a constant factor of n for large n即可。

通过这种方式可以很容易描述的想法，像f1 = n^2 + 2二次函数总是比喜欢f2 = 10000*n + 50000任何线性函数较大，当n足够大，可以通过写F1为O(n)和f2为O(n^2)。