Сложность времени и пространства При перетасовке списка в Python (без использования встроенной функции)

Question

Я сейчас изучаю Python,

Я хотел бы реализовать функцию, которая принимает список целых чисел (при условии, что он имеет N элементов) И распечатывает этот список случайным образом и без повторений.

Я пытался использовать идеи, которые я прочитал здесь на сайте, и реализовал две функции,

Я буду рад понять для каждой функции, что такое время и пространство сложности?

спасибо заранее,

import random
def shuffle1(arr):
    for n in range(len(arr) - 1):
        rnd = random.randint(0, (len(arr) - 1))
        val1 = arr[rnd]
        val2 = arr[rnd - 1]

        arr[rnd - 1] = val1
        arr[rnd] = val2

    print(arr)

Arr1 = [1, 2, 3, 4, 5]
shuffle1(Arr1)

---

import random
def shuffle2(Arr):
    result = []
    while len(Arr) > 0:
        index = random.randrange(0,len(Arr))
        result.append(Arr.pop(index))
    print(result)


Arr1 = [1, 2, 3, 4, 5]
shuffle2(Arr1)

Answer 1

Мое предположение (которое должно быть разумным) состоит в том, что random.randint(0, n) имеет временную сложность, пропорциональную числу битов в n.

Сложность выражается как функция размера ввода.
В первом случае у вас есть цикл, который выполняется n раз, при этом n является размером списка, а внутри у вас есть вызов random.randint с линейным числом битов длины списка. Таким образом, у вас есть O(nlogn). То есть вы выполняете n раз logn операцию.

Во втором случае вы используете pop (см. здесь ), который в худшем случае может быть O(k) с k<=n. Следовательно, время работы составляет O(n^2). Вы можете думать об этом как (n+log(n)+(n-1)+log(n-1)+…+1+log(1)).
O(n^2) - худший случай , лучший случай (в котором вы всегда выбираете последний элемент списка с измененным размером) - O(nlogn) (см. приближение Стирлинга для более подробной информации).

Например, этот алгоритм имеет O(f) сложность времени, так как число итераций равно 10 ^ 9 независимо от того, где f - сложность времени random.sample().

import random

def shuffle1(lst):
    for _ in range(1000000000):
        pos1, pos2 = random.sample(range(len(lst)),2) 
        lst[pos1], lst[pos2] = lst[pos2], lst[pos1]

Сложность пространства относится к размеру рабочей памяти, необходимой алгоритму относительно размера ввода.
В первом случае вы используете O(1) вспомогательное пространство, т. Е. Всего две переменные для хранения значений в двух позициях, которые нужно поменять местами (постоянное число). Обратите внимание, что размер списка ввода не учитывается.
Во втором случае вы создаете новый список размером n, таким образом O(n).