复杂性分析：如何识别"basic operation"？

Question

我正在参加 class 复杂性分析，我们尝试确定算法的基本操作。我们定义如下：

A basic operation is one that best characterises the efficiency of the particular algorithm of interest

For time analysis it is the operation that we expect to have the most influence on the algorithm’s total running time:
- Key comparisons in a searching algorithm
- Numeric multiplications in a matrix multiplication algorithm
- Visits to nodes (or arcs) in a graph traversal algorithm

For space analysis it is an operation that increases memory usage
- A procedure call that adds a new frame to the run-time stack
- Creation of a new object or data structure in the run-time heap

The basic operation may occur in more than one place in the algorithm

所以我想弄清楚 ReverseArray 算法的基本操作。

ReverseArray(A[0..n-1])
for i=0 to [n/2]-1 do
   temp <- A[i]
   A[i] <- A[n-1-i]
   A[n-1-i] <- temp

我的导师提到一个基本操作是 "kind of operation"，比如赋值、加法、除法，在这个算法的情况下，我可以在赋值或减法之间进行选择。

现在我有一个练习，询问给定算法的基本操作。那么说基本操作是 "assignment" 然后列出 for 循环内的所有 3 行代码是否正确？

我觉得也可以是减法，因为有4个。

我不太确定基本操作是一个普遍认可的术语，还是我的讲师选择的一个表达方式。

Answer 1

您可以将任何操作（赋值、读取数组访问、减法）作为基本操作。所有都会导致相同的结果：

赋值：3 * n/2 -> O(n)
读取权限：2 * n/2 -> O(n)
完整的 for 块：n/2 -> O(n)

这对您的示例没有影响。这是一个愚蠢的例子（没有优化代码），它有所不同：

for i = 1 to n do
    x = a[i]
    for j = 1 to n do
        b[j] += x

显然，对数组a的读访问需要O(n)步，其中写操作或加法的次数为O(n^2) 。

基本操作是您计算复杂度所依据的操作。这可以是代码中的每个操作，但这会导致不同的结果，如我在示例中所示。

出于这个原因，人们经常看到这样的短语：
代码需要 O(n) 次乘法 和 O(n^2) 次加法.

复杂性分析：如何识别"basic operation"？

Complexity Analysis: how to identify the "basic operation"?

complexity-theory

time-complexity