1
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);
}
私はこれらの2つの方法を持っています。私が理解できないことは、両方に再帰がありますが、なぜ最初のものが線形で、2番目の方法が線形であるということですか？ 除算または乗算がある場合、通常はランタイムがlog-nであると言われました。第1の方法は除算を有するが、それはまだ線形とみなされるが、第2の方法は線形ではない。これらの漸近表記とそのランタイムについては混乱しています
私が理解するほど、それは私を混乱させ、私が何も知らないように感じさせます。