Нахождение временной сложности алгоритма - PullRequest
Новая
       51

Нахождение временной сложности алгоритма

0 голосов
/ 06 мая 2020

Мне нужно написать алгоритм, который находит длину l oop в связанном списке и возвращает (если l oop существует), а также возвращает элемент в l oop. если в списке нет l oop, вернуть None. вот мой код: 

def find_circle(self):
    slower = self.head
    faster = self.head
    while (slower is not None and faster is not None):
        if faster.next is not None:
            faster = faster.next.next
        slower = slower.next
        if slower == faster:
            counter = 1
            slower = slower.next
            while slower != faster:
                slower = slower.next
                counter += 1
            return counter, slower.data
    return None

код должен иметь временную сложность O (n) и дополнительную пространственную сложность O (1). Соответствует ли этот код временной и пространственной сложности?

1 Ответ

0 голосов
/ 07 мая 2020

Да, временная сложность приведенного выше кода O(n), а пространственная сложность O(1), поскольку вы не сохраняете весь список. 

def find_circle(self):
    // Space O(1)
    slower = self.head
    faster = self.head

    // Looping through only once, hence time complexity is O(n)
    while (slower is not None and faster is not None):
        if faster.next is not None:
            faster = faster.next.next
        slower = slower.next
        if slower == faster:
            counter = 1
            slower = slower.next
            while slower != faster:
                slower = slower.next
                counter += 1
            return counter, slower.data
    return None
...