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,虽然第一种方法有除法,但它仍然被认为是线性的,而第二种方法没有。
我越是明白,就越让我困惑,让我觉得自己什么都不知道。

最佳答案

第一种方法的公式是:
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)时间复杂度。主定理同样适用于此。注意,在第一种情况下,虽然树(用于公式)将具有O(log n)级别,但在每个级别中,您将花费与该级别上的节点数成比例的时间,而不是O(n)。

10-08 05:18
查看更多