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

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(。您也可以使用主方法来解决此问题。

但对于第二个是：

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

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