новой информатики здесь, так что я написал этот пузырь код сортировки и пытаюсь вычислить это время сложность и производительность здесь, код для сортировки здесь:Является ли моя временная сложность правильной для моего кода сортировки пузыря?
for (int i = 0; i < size; i++)
{
Node current = head.next;
while (current.next != tail)
{
if (current.element.depth < current.next.element.depth)
{
swap(current, current.next);
}
else
{
current = current.next;
}
}
}
Код метода подкачки здесь:
void swap(Node nodeA, Node nodeB)
{
Node before = nodeA.prev;
Node after = nodeB.next;
before.next = nodeB;
after.prev = nodeA;
nodeB.next = nodeA;
nodeB.prev = before;
nodeA.prev = nodeB;
nodeA.next = after;
}
Теперь я знаю, что временная сложность в пузырьковой сортировке находится в производительности наихудшей O(n^2), но я пытаюсь вычислить функцию каждых расстрелов по моему для цикла здесь. У меня есть базовое понимание временной сложности, я знаю, что стандарт для цикла равен f(n) = 2n + 2, и мы рассматриваем худший сценарий временной сложности. До сих пор это моя мысль прогресса, чтобы найти f(n) моего кода:
int i = 0; This will be executed only once.
i < size; This will be executed N+1 times.
i ++; This will be executed N times.
current = head.next; This will be executed N times.
current.next != tail; This will be executed N times.
And since a while loop is within the for loop,
it's n*n within the while loop, there
are 4 operations, so it's 4n^2.
В худшем случае, я буду использовать метод SWAP каждый раз, и так как мое время сложность для метода подкачки просто 8 (я думаю, это только 8 исполнений правильно?) Итак, худший сценарий для swap(current,current.next) - 8n?
Если мы добавим их:
f(n) = 1 + n + 1 + n + n + n+ 4n^2 + 8n
f(n) = 4n^2 + 12n + 2
f(n) ~ O(n^2)
ли мое время сложность f(n) правильно?
Если нет, можете ли вы указать мне правильный ответ, пожалуйста, также есть ли у вас предложения по улучшению производительности моего кода?