Какова временная сложность алгоритма связанного списка ниже - PullRequest
Новая
       28

Какова временная сложность алгоритма связанного списка ниже

0 голосов
/ 27 июня 2019

Я пишу алгоритм для удаления последних N узлов из связанного списка и добавления его в начало связанного списка, как указано ниже 

func removeAndAppendLastToFront(N: Int) {
    var slow: Node? = head
    var fast: Node? = head

    for _ in 0 ..< N - 1 {
        fast = fast?.next
    }

    var previous: Node?
    while fast?.next != nil {
        previous = slow
        slow = slow?.next
        fast = fast?.next
    }

    if previous != nil {
        previous?.next = nil
        fast?.next = head
        head = slow
    }
}

Однако мне сложно вычислить временную сложность этого алгоритма.

Согласно моему пониманию, первый цикл for должен быть константой O (1) 

 for _ in 0 ..< N - 1 {
        fast = fast?.next
 }

Но как насчет второго цикла while, будет ли это O (log N), учитывая, что быстрый указатель был перенаправлен за линейное время в течение первого цикла for, а второй цикл while просто продолжается с последнего сохраненного значения? 

  while fast?.next != nil {
        previous = slow
        slow = slow?.next
        fast = fast?.next
  }

И какова будет общая временная сложность этого алгоритма?

1 Ответ

1 голос
/ 27 июня 2019

как твой первый цикл O (1), когда он идет от начала до n-го элемента? и так как n - ваш последний элемент, вы практически повторяете весь список Ваш первый цикл на самом деле имеет O (N), и, поскольку вы находитесь в конечном элементе, он не должен иметь следующего элемента и не должен делать быстро? .next! = nil условие false?

...