识别算法的基本操作

Question

我目前正在大学学习一个算法单元，我似乎无法从任何人那里得到一个关于确定算法的基本操作的明确答案。我知道它可以发生在一个以上的地方，但在考虑最好的情况、一般的情况和最坏的情况时，情况会有所不同吗？

在下面的示例中，我是否正确地假设Ai = Null是最佳情况的基本操作，因为它是给出最佳执行时间的操作？

对于最坏的情况，Ai =0是基本操作吗?因为它的代码块将有最大的执行时间吗？普通的案子呢？这将是与数组的所有4个比较吗？就像我说的，我似乎无法从任何人那里得到一个明确的答案。就连我读过的教科书都非常模糊。任何帮助都将不胜感激。

for i <- 0 to n-1
    if A[i] = Null
       return
    else
       if A[i] < 0
          .....
          .....
          .....
       else if A[i] = 0
          for j <- 0 to n-1
             .....
             .....
             .....
       else if A[i] > 0
          .....
          .....
          .....

Answer 1

O表示法是表示执行时间a.k.a的函数。时间复杂性。随着输入大小的增加，n项将成为最主要的项。由这个占主导地位的术语所代表的运算称为基本运算。

假设示例中的所有点都是O(1)，这些点是您的基本操作。

• In a[0] == null情况最好的情况是O(1) (因为它似乎代表丢失的数据)，
• 对于每个I，最坏的情况复杂度是O(n^2)，
• 对于每个I来说是随机值，平均情况是O(n) (虽然一些值包含一个0，平均值可能略高于O(N))

f 210

Answer 2

控制算法性能的操作有时称为基本操作。在您的例子中，这是对Ai的评估。根据n次迭代的结果，算法的性能将有所不同。如何经常通过指定三个角落的情况-最好的，最坏的，和平均。在这里，它取决于Ai计算为零的频率--从不、始终或平均(假设某种分布)。性能用大-O表示法来指定，但不一定。

因此，基本操作设置了性能，这三个性能案例说明了它是如何运行的。