карта уменьшить сложность - PullRequest
Новая
       22

карта уменьшить сложность

1 голос
/ 28 декабря 2010

Предположим, что у меня есть этот вход: список списка

(def list-of-list-3 (список (список 1 2 3) (список 4 5 6)(список 7 8 9)))

(карта № (сокращение *% 1) список-списка3)

Карта-уменьшение имеетO (n ^ 2) сложность в этом случае?

преобразование карты переводится как два вложенных для?

Так, когда я запускаю приведенный выше пример наВ ответной реплике время сложности выглядит как O (n).

, когда я дублирую размер ввода (list-of-list-6 (list (list 1 2 3) (list 4 5 6) (list 4 5 6) (list7 8 9) (список 8 2 3) (список 9 8 1) (список 7 6 4))) время увеличивается линейно, а не квадратично.

Кто-нибудь может сказать почему?

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

Ответы [ 2 ]

4 голосов
/ 28 декабря 2010

Это не O (n ^ 2), это примерно O (n * m), где n - это число списков, а m - их длина.Будут и другие факторы, связанные с длинами различных чисел.Сделайте это вручную и сами убедитесь, почему!

2 голосов
/ 28 декабря 2010

Снижение карты в этом случае имеет сложность O(n^2)?

Невозможно сказать, если вы не скажете нам, что n соответствует выражению list-of-list-3.

Кстати, O(n^2) или O(n*n) - это квадратичная сложность, а не экспоненциальная сложность.Экспоненциальная сложность это O(e^n).

, когда я [удваиваю] входной размер 

( list-of-list-6 (list (list 1 2 3) (list 4 5 6) ( list 7 8 9) 
                       (list 8 2 3) (list 9 8 1) (list 7 6 4)) )

время увеличивается линейно, а не экспоненциально.

Исходя из этого, я предполагаю, что n должно быть длиной внешнего списка.Если так, то reduce на самом деле O(n), а не O(n^2).Чтобы получить квадратичный рост, вам нужно определить list-of-list-6 как: 

( list-of-list-6 (list (list 1 2 3 4 5 6) (list 4 5 6 1 3 2) 
                       (list 7 8 9 1 2 3) (list 8 2 3 2 3 4) 
                       (list 9 8 1 2 3 4) (list 7 6 4 5 6 7)) )
...