Итак, у меня есть задание из моей школы, и мне было только интересно, какая сложность времени у моего алгоритма (не требуется для ответа как такового, только алгоритм должен работать быстрее, чем O (n) в худшем случае))
Вопрос заключается в следующем: учитывая n (n ≥ 3) различных элементов, разработайте алгоритм «разделяй и властвуй» для вычисления первых трех наименьших элементов.Ваш алгоритм должен возвращать тройку (x, y, z), такую что x
И мое решениеследует:
Solution: Since “n” must be ≥ 3, the given array cannot have less than 3
elements.
If n == 3, simply compare the elements to each other (maximum of 3
comparisons needed).
Compare the first 2 elements to each other and assign the elements with a
“smallest element” and “2nd smallest element”, we’ll call
them “x” (smallest) and “y” (2nd smallest) from here on out. Compare “x”
(smallest) to the 3rd element.
If x > 3rd element, we know that the 3rd element is the smallest in this
array, therefore: “y” becomes the new “z”, “x” becomes the new “y”, and the
3rd element becomes the new “x”. You’re now left with the desired output.
Return the triple (x<y<z). (2 comparisons used)
Else if x < 3rd, make the 3rd element be “z”. Compare y with 3rd element
(now “z”).
If y < z, do nothing, you already have a triple with the desired outcome
(x<y<z).
If y > z, swap the elements. You now have a triple with the desired outcome
(x<y<z).
Теперь, когда первый случай (n == 3) был обработан, давайте разберемся, что должно произойти, когда n> 3.
If n > 3, split the array recursively into parts of n/2 (if n is an uneven
number, split the array into parts of n/2 + 1 & n/2).
Keep doing the 1st step until the split arrays have a size of ≥ 2.
Compare the elements in each sub-array to each other, and assign a lowest
and 2nd lowest value to them. (“x” and “y”)
When merging the sub-array, compare the lowest element of one sub-array, to
the other array’s lowest value.
If a1(lowest) < a2(lowest), make a1(lowest) be “x”, a2(lowest) the new “y”,
and a2(2nd lowest) the new “z”, then compare a1(2nd lowest) with the highest
value in a1 at that moment (“z” in this case).
If a1(2ndlowest) > “z”, do nothing. (“x”, “y” and “z” are already the three
lowest values in the sub-array)
Else if a1(2ndlowest) < “z”, swap the elements and make a1(2ndlowest) the
new “z”, then compare the new “z” with “y”
If “z” < “y”, swap the elements.
No more comparisons needed, as the “x” is the lowest element from a1, which
means the 3 elements, “x”, “y” & “z” are now the lowest possible from this
subsection of the array.
Repeat from step 4 until reaching the highest layer of the call, and you now
have a triple that satisfies the condition (x<y<z).
Извините за стенутекст (и псевдокод).Я читал о сложности времени, и я понимаю простые (например, оператор имеет постоянное время, цикл for имеет время в зависимости от того, как долго он и т. Д.), Но мне трудно понять сложность времени для моегособственный алгоритм.Заранее спасибо.