Какова продолжительность этого Haskell слияния кода

Question

Я придумал этот код, который принимает два SORTED в списках возрастающего порядка, а затем объединяет эти два списка в один список, сохраняя восходящий порядок-или сравнение. Я пытался проанализировать его и посмотреть, какова его временная сложность. Я убежден, что в худшем случае нам придется проходить через все списки, и поскольку есть 2 списка, нам нужно иметь вложенную рекуранс, что означает время O (n^2) для случая WORST. Однако, поскольку мы сравниваем размеры каждого из двух элементов, прежде чем мы рекурсируем, я думаю, что это, вероятно, время O (log n). Поправьте меня, если я ошибаюсь. Благодаря

Вот моя рекурсия:

mergeLists::[Integer]->[Integer]->[Integer] 
mergeLists [] []  =[] 
mergeLists [] (y:ys) =(y:ys) 
mergeLists (x:xs) [] =(x:xs) 

mergeLists (x:xs) (y:ys) 
|(x<y)     =x:mergeLists xs (y:ys) 
|otherwise    =y:mergeLists (x:xs) ys 

Answer 1

Эффективность времени будет O (п), так как эти два списка, как предполагается, будет в порядке возрастания уже. Вам не нужно повторять или выполнять какую-либо часть сравнения больше, чем количество элементов в каждом списке, переданных функции.

Ach, Kareem уже ответил на вопрос. Я сделаю это лучше, предоставив понимание нотации Big-O для экономии времени и пространства. Big-O Notation используется для представления базовой концепции алгоритмической производительности по набору данных произвольного размера. Очевидно, что с увеличением набора данных для работы алгоритма фактическое время выполнения операции увеличивается. Если увеличение времени определяется линейно (IE каждый элемент данных увеличивает фактическое время алгоритмов до равного количества, как и все остальные элементы), то эффективность времени алгоритма называется «на порядок n» или O (n). Это относится к вашему алгоритму.

Чтобы узнать больше о Big-O нотации, больше читать на другой вопрос здесь, на StackOverflow: What does O(log n) mean exactly?

Answer 2

как перечисленные уже отсортировано .. то время слияния будет O (п) при п общего размера двух списков.

он будет работать, как сортировки слияния: http://www.vogella.com/tutorials/JavaAlgorithmsMergesort/article.html

Answer 3

Ваш mergeLists будет принимать O (п + т) где п и м являются длины входного списка. Это легко доказать математической индукцией по n + m, что число рекурсивных вызовов будет не более n + m.

• В течение первых 3 случаев нет рекурсии, так что число рекурсивных вызовов тривиального меньше, чем п + т.
• Для последних 2 случаев: в каждом случае вложенный вызов получает один из исходных списков, а другой сокращен на 1. Таким образом, мы можем использовать принцип индукции, который говорит нам, что вложенный вызов будет составлять не более n + m-1 рекурсивных вызовов, и поэтому соответствующий вызов составит не более n + m звонки.