В моем учебнике по алгоритмам для практики есть вопрос, в котором я не уверен, и надеялся, что кто-то сможет уточнить/объяснить:
Когда вы разрабатываете алгоритм «разделяй и властвуй» для хранения элементов в связанном списке размера n, будет ли разделение задачи пополам асимптотически быстрее в худшем случае, чем алгоритм, разделяющий список на одну подзадачу размера 1 и другую подзадачу размера п-1?
рассматривайте процесс как древовидную структуру, например:
[1, n]
/ \
[1, n/2] [n/2, n]
/ \ / \
[1, n/4] [n/4, n/2] [n/2, n*3/4] [n*3/4, n]
стоимость времени зависит от того, сколько вычислений вы делаете на каждом уровне.
например найти максимальное число в массиве.
int f1(int a[], int n){
if (n == 1) return a[0];
return max(a[0], f1(a + 1, n - 1));
}
int f2(int a[], int n){
if (n == 1) return a[0];
return max(f2(a, n / 2), f2(a + n / 2, n - n / 2));
}
расчет, который вы делаете на каждом уровне, равен O(1), поэтому и f1, и f2 в сумме составляют O(n).
или, как вы упомянули, алгоритм quicksort, расчет, который вы делаете на каждом уровне, равен O(n), поэтому общая стоимость зависит от количества уровней.
если мы разделим его на [1, n/2] и [n/2, n], будет O(logn) уровней, а общая стоимость времени составит O(nlogn).
и если мы разделим его на [1, 1] и [2, n], то будет O(n) уровней, так что общая стоимость времени будет O(n^2)
