Мастер-теорема, дающая неверный ответ [дубликат]
Я думаю, что самый простой способ сделать это - сделать новую ветку от мастера и выполнить слияние --squash ветки функции.
git checkout master
git checkout -b feature_branch_squashed
git merge --squash feature_branch
Тогда у вас есть все изменения, готовые для фиксации.
4 ответа
Каждое сравнение алгоритма O(n) [сравнение двух строк - O(n) наихудший случай - вы можете обнаружить, что «больше» только для последнего символа], вы имеете O(nlogn) сравнения в mergesort.
Таким образом, вы получаете O(nlogn * n) = O(n^2 * logn)
Но согласно рекуррентному соотношению
T (n) = 2T (n / 2) + O (m * n)
Будет T (n) = 2T ( n / 2) + O (n ^ 2), когда m = n
Тогда результатом будет O (n ^ 2), а не O (n ^ 2logn).
Исправить если я ошибаюсь.
-
1– user567879 16 February 2012 в 05:34
**answer is O(n^2logn)
,
we know Merge sort has recurrence form
T(n) = a T(n/b) + O(n)
in case of merge sort
it is
T(n) = 2T(n/2) + O(n) when there are n elements
but here the size of the total is not "n" but "n string of length n"
so a/c to this in every recursion we are breaking the n*n elements in to half
for each recursion as specified by the merge sort algorithm
MERGE-SORT(A,P,R) ///here A is the array P=1st index=1, R=last index in our case it
is n^2
if P<R
then Q = lower_ceiling_fun[(P+R)/2]
MERGE-SORT(A,P,Q)
MERGE-SORT(A,Q+1,R)
MERGE (A,P,Q,R)
MERGE(A,P,Q,R) PROCEDURE ON AN N ELEMENT SUBARRAY TAKES TIME O(N)
BUT IN OUR CASE IT IS N*N
SO A/C to this merge sort recurrence equation for this problem becomes
T(N^2)= 2T[(N^2)/2] + O(N^2)
WE CAN PUT K=N^2 ie.. substitute to solve the recurrence
T(K)= 2T(K/2) + O(K)
a/c to master method condition T(N)=A T(N/B) + O(N^d)
IF A<=B^d then T(N)= O(NlogN)
therefore T(K) = O(KlogK)
substituting K=N^2
we get T(N^2)= O(n*nlogn*n)
ie.. O(2n*nlogn)
.. O(n*nlogn)
, следовательно, решена
Отношение повторения временной сложности равно
T (a, b) = 2T (a / 2, b) + O (b ^ 2)
Так ясно, что высота дерева будет logn. Таким образом, сложность времени равна O (n ^ 2 * logn).