确定比较两个数组的算法的运行时间
我想知道如何确定用伪代码编写的算法的运行时间，以便我可以熟悉运行时间。例如，您如何知道比较两个数组以确定它们是否不相同的算法的运行时间是多少？
数组 1 = [1, 5, 3, 2, 10, 12] 数组 2 = [3, 2, 1, 5, 10, 12] 所以这两个数组不一样，因为它们的顺序不同。
我的伪代码是：
1）将当前指针设置为第一个数组中的第一个数字
2）将第二个指针设置为第二个数组中的第一个数字
3) while (当前指针!= " ") 与其他数组中相同位置的元素进行比较
4) if (当前指针==第二个指针)
将当前指针移至下一个数字 将第二个指针移动到下一个数字
5) else (输出数组不相同) 所以
我首先假设我的代码是正确的。我知道步骤 4 只执行一次，因为只需要 1 次匹配即可显示数组不相同。因此第 4 步只需要常数时间 (1)。我知道步骤 1 和 2 也只执行一次。
到目前为止我知道运行时间是 3 + ？ （？是循环本身的运行时间）
现在我迷失了循环部分。循环是否运行 n 次（n 是数组中的数字数量？），因为最坏的情况可能是每个数字都匹配？我是否以正确的方式考虑运行时间？
如果有人可以帮助解决这个问题，我将不胜感激。
谢谢！
I want to know how it is possible to determine the run time of an algorithm written in pseudocode so that I can familiarize myself with run time. So for example, how do you know what the run time of an algorithm that will compare 2 arrays to determine if they are not the same?
Array 1 = [1, 5, 3, 2, 10, 12] Array 2 = [3, 2, 1, 5, 10, 12]
So these two arrays are not the same since they are ordered differently.
My pseudocode is:
1) set current pointer to first number in first array
2) set second pointer to first number in second array
3) while ( current pointer != " ") compare with same position element in other array
4) if (current pointer == second pointer)
move current pointer to next number
move second pointer to next number
5) else (output that arrays are not the same)
end loop
So I am assuming first off my code is correct. I know step 4 executes only once since it only takes 1 match to display arrays are not the same. So step 4 takes only constant time (1). I know step 1 and 2 only execute once also.
so far I know run time is 3 + ? (? being the run time of loop itself)
Now I am lost on the loop part. Does the loop run n times (n being number of numbers in the array?), since worst case might be every single number gets matched? Am I thinking of run time in the right way?
If someone can help with this, I'll appreciate it.
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您所询问的称为算法的时间复杂度。我们使用所谓的 Big-O 表示法来讨论算法的时间复杂度。
Big-O 表示法是一种讨论我们的算法相对于算法输入的大小所采取的近似步数的方法，在该大小的输入的最坏可能情况下。
您的算法在
O(n)时间内运行（发音为“big-oh of n”或“order n”，有时我们只是说“线性时间”）。您已经知道，步骤 1、2 和 4 都以相对于数组大小而言恒定的步骤数运行。我们说这些步骤在
O(1)时间内运行（“恒定时间”）。那么让我们考虑第 3 步：
如果数组中有 n 个元素，那么在最坏的情况下第 3 步需要进行 n 次比较。所以我们说第 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 变得越来越微不足道，5 也是如此。因此，我们只需将函数简化为f is inside a对于大 n来说 n 的常数因子，通过说f 在 O(n)中。通过这种方式，很容易描述这样的想法：像
f1 = n^2 + 2这样的二次函数总是大于像f2 = 10000*n + 50000这样的任何线性函数当 n 足够大时，只需将 f1 写为O(n)，将 f2 写为O(n^2)。What you are asking about is called the time-complexity of your algorithm. We talk about the time complexity of algorithms using so called Big-O notation.
Big-O notation is a method for talking about the approximate number of steps our algorithms take relative to the size of the algorithms input, in the worst possible case for an input of that size.
Your algorithm runs in
O(n)time (pronounced "big-oh of n" or "order n" or sometimes we just say "linear time").You already know that steps 1,2, and 4 all run in a constant number of steps relative to the size of the array. We say that those steps run in
O(1)time ("constant time").So let's consider step 3:
If there are n elements in the array, then step 3 needs to do n comparisons in the worst case. So we say that step 3 takes
O(n)time.Since the algorithm takes
O(n)time on step 3, and all other steps are faster, we say that the total time complexity of your algorithm isO(n).When we write
O(f), wherefis some function, we mean that the algorithm runs within some constant factor offfor large values.Take your algorithm for example. For large values of n (say n = 1000), the algorithm doesn't take exactly n steps. Suppose that a comparison takes 5 instructions to complete in your algorithm, on your machine of choice. (It could be any constant number, I'm just choosing 5 for example.) And suppose that steps 1, 2, 4 all take some constant number of steps each, totalling 10 instructions for all three of those steps.
Then for n = 1000 your algorithm would take:
Steps 1 + 2 + 4 = 10 instructions. Step 3 = 5*1000 = 5000 instructions.
This is a total of 5010 instructions. This is about 5*n instructions, which is a constant factor of
n, which is why we say it isO(n).For very large n, the 10 in
f = 5*n + 10becomes more and more insignificant, as does the 5. For this reason, we simply reduce the function tof is within a constant factor of n for large nby sayingf is in O(n).In this way it's easy to describe the idea that a quadratic function like
f1 = n^2 + 2is always larger than any linear function likef2 = 10000*n + 50000when n is large enough, by simply writing f1 asO(n)and f2 asO(n^2).你是对的。运行时间为 O(n)，其中 n 是数组中元素的数量。每次向数组添加 1 个元素，在最坏的情况下都必须再执行循环 1 次。
You are correct. The running time is O(n) where n is the number of elements in the arrays. Each time you add 1 element to the arrays, you would have to execute the loop 1 more time in the worst case.