algorithm - 对这些渐近符号及其运行时感到困惑

Question

public static Asymptotic f3_notation = Asymptotic.BIG_THETA;
public static Runtime f3_runtime = Runtime.LINEAR;
/* When f3 is first called, start will be 0 and end will be the length of the array - 1 */
public int f3(char[] array, int start, int end) {
    if (array.length <= 1 || end <= start){
        return 1;
    }

    int mid = start + ((end - start) / 2);

    return f3(array, start, mid) + f3(array, mid + 1, end);
}

public static Asymptotic f4_notation = Asymptotic.BIG_THETA;
public static Runtime f4_runtime = Runtime.LINEARITHMIC;
/* When f4 is first called, start will be 0 and end will be the length of the array - 1 */
public int f4(char[] array, int start, int end) {
    if (array.length <= 1 || end <= start) return 1;

    int counter = 0;

    for (int i = start; i < end; i++) {
        if (array[i] == 'a') counter++;
    }

    int mid = start + ((end - start) / 2);

    return counter + f4(array, start, mid) + f4(array, mid + 1, end);
}

所以我有这两种方法。我不明白的是两者都有递归但为什么第一个是线性的而第二种方法是线性的？ 有人告诉我，如果有除法或乘法，通常它的运行时间是 log-n。虽然第一种方法有除法，但它仍然被认为是线性的，而第二种方法不是。

越了解越迷茫，感觉自己什么都不懂。

Answer 1

第一种方法的公式是:

T(n) = 2T(n/2) + O(1)

因此，如果您为该公式绘制相应的树，您将看到工作量与树中的节点数成正比，即 O(n)。你也可以使用 Master Method解决这个问题。

但是第二个是:

T(n) = 2T(n/2) + O(n)

事实上，这里发生的是你的树将有(就像第一种方法)O(log n) 级别，但是在每个级别你花费 O(n) 时间，这将导致 O(n log n) 时间复杂度。 Master Theorem 同样适用于此。请注意，在第一种情况下，尽管您的树(对于公式)将具有 O(log n) 级别，但在每个级别中，您将花费与该级别上的节点数成比例的时间，而不是 O(n)。