Единые связанные списки и временная сложность - PullRequest
Новая
       27

Единые связанные списки и временная сложность

0 голосов
/ 12 июля 2020

Я только начинаю свое путешествие с topi c структур данных и работаю с некоторыми односвязными списками. Я создал два типа списков:

  1. Где узлы добавляются в начало списка, проверяемого из хвоста (временная сложность O (n))
  2. Где узлы добавляются к заголовок списка проверяет только заголовок (временная сложность O (1))

Я хотел запустить тест и проверить вывод моего кода и более или менее он верен, но я заметил эти странные шумы и я не знаю, почему они там. Вы, ребята, знаете об этом? 

class Node(object):
        def __init__(self, data = None):
            self.data = data
            self.next = None

        def _str_(self):
            return str(self.data)


class SonglyLinkedList_tail:
        def __init__(self):
            self.tail = None
            self.size = 0

        def append(self, data):
            node = Node(data)
            if not self.tail:
                self.tail = node
            else:
                current = node
                while current.next:
                    current = current.next
                current.next = node
            self.size += 1

class SinglyLinkedList_head:
        def __init__(self):
            self.tail = None
            self.head = None
            self.size = 0

        def append(self, data):
            node = Node(data)
            if self.head:
                self.head.next = node
                self.head = node
            else:
                self.head = node
                self.tail = node
            self.size += 1

        def iter(self):
            current = self.tail
            if current.next:
                val = current.data

                current = current.next

tail = SonglyLinkedList_tail()
head = SinglyLinkedList_head()
xes = []
yes = []
for i in range(5000):
        xes.append(i)
        list = random.sample(range(1, 100000), i)
        start_time = float(time.time())
        stop_time = float(time.time())
        for number in list:
            tail.append(number)
        stop_time = time.time()
        run_time = stop_time-start_time
        yes.append(run_time)

Временная сложность для алгоритма O (n) Временная сложность для алгоритма O (1)

РЕДАКТИРОВАТЬ:

Фотография после предложенных изменений в алгоритме 1 Временная сложность первого алгоритма O (n ^ 2)

1 Ответ

0 голосов
/ 13 июля 2020

Я могу найти две ошибки в вашем коде, которые могут привести к ошибкам. Во-первых, внутри метода добавления функции SinglyLinkedList_tail вы выполняете current = node, что неверно. Потому что «узел» только что был создан, и через него вы не можете перемещаться по связанному списку. Переменная current должна быть инициализирована с помощью tail. Правильный способ: 

class SonglyLinkedList_tail:
    def __init__(self):
        self.tail = None
        self.size = 0

   def append(self, data):
       node = Node(data)
       if not self.tail:
            self.tail = node
       else:
            current = tail
            while current.next:
                current = current.next
            current.next = node
       self.size += 1

Во-вторых, метод добавления функции SinglyLinkedList_head имеет аналогичную проблему. Его правильная реализация может быть: 

def append(self, data):
    node = Node(data)
       if self.head:
            node.next = self.head.next
            self.head = node
       else:
            self.head = node
            self.tail = node
       self.size += 1
...