Какова временная сложность обхода Морриса o (n)?

Во-первых, у меня есть исправление, чтобы сделать заявление, которое вы сделали:

При обходе, когда у узла есть левый потомок, его копия делается правому потомку его Предшественник

Копия [текущего] узла не сделана правому дочернему элементу его предшественника [текущего узла] - правый дочерний элемент предшественника текущего узла равен указал на текущий узел - указатель не делает никакой копии; вместо этого он просто указывает на текущий узел, который уже существует .

Теперь, чтобы ответить на ваш вопрос о вашем фрагменте кода:

while(pre->right != NULL && pre->right != current)
        pre = pre->right;

• Этот цикл действительно добавляет время на выполнение алгоритма [по сравнению с тем, что цикл не был в коде]
• Но в худшем случае время, которое оно добавляет, составляет ровно n (принимая время выполнения от n до 2n ). Этот наихудший случай случается, когда каждый отдельный узел должен посещаться в дополнительное время, чтобы найти всех предшественников; Кстати, каждое такое дополнительное посещение данного узла - это только дополнительное время, которое он посещает при поиске предшественников (это потому, что обнаружение любого другого предшественника никогда не пройдет по тем же узлам, которые прошли через, чтобы найти любого другого предшественника) - это объясняет, почему дополнительное время способствует переходу от n -> 2n [линейный], но не n -> n ^ 2 [квадратичный]
• Даже если 2n > n , когда [Big-O] сложность рассматривается , O (2n) = O (n)
• Другими словами, более длительное время 2n по сравнению с n не является реальной дополнительной сложностью ]: n & amp; 2n runtimes оба имеют сложности одинаковых O (n) [они оба «линейны»]

Теперь, даже если это звучало так, как я подразумевая выше, что время выполнения всего алгоритма равно 2n , это не так - это фактически 3n .

• Цикл, который находится в только фрагмент кода , сам вносит n время
• Но алгоритм в целом работает в 3n , потому что каждый узел посещается не более 3 раз (один раз / сначала, чтобы «нанизывать» его обратно на узел, для которого он является предшественником (конечная цель, которой помогает фрагмент кода); 2-й раз, когда он достигается в обычном обходе [в отличие от чего-либо, что связано с потоковой обработкой предшественника]; и затем 3-й / последний раз, когда он снова обнаруживается как предшественник [который сам на 2-й / последний раз] снова и его правый дочерний указатель / поток удаляется из указания на правый дочерний элемент текущего узла [непосредственно перед печатью текущего узла] }
• И снова [точно так же, как сложность O (2n) = O (n)], сложность O (3n) = O (n)
• Итак, подведем итог: Да, ваш цикл фрагмента кода вносит вклад в время , но НЕ в дополнительное время сложность

Между прочим, я не думаю, что эта строка (из полного алгоритма) для удаления старой ссылки на «нить» предшественника является строго необходимой (хотя это не повредит, и может считаться хорошим исправлением) :

pre->right = NULL;