вычислить время работы функции

Question

У меня возникли проблемы с приближением времени работы функции, вызывающей другие функции. Например, здесь это функция, которая преобразует бинарное дерево в список:

(define (tree->list-1 tree) 
    (if (null? tree) 
    ’() 
    (append (tree->list-1 (left-branch tree)) 
      (cons (entry tree) 
      (tree->list-1 (right-branch tree)))))) 

Объяснение Т (п) = 2 * Т (п/2) + O (N/2), так как процедура Append принимает линейное время. Решая выше уравнение, получаем T (n) = O (n * log n).

Однако минусы также являются процедурой, которая объединяет два элемента. В этом случае он проходит через все входные узлы, почему бы нам не добавить еще один O (n) в решении?

Благодарим за помощь.

Answer 1

Рассмотрите O(n^2) который явно квадратный. Теперь рассмотрим O(n^2 + n), это все равно квадратично, поэтому мы можем уменьшить это до O(n^2), так как + n не имеет значения (он не меняет «по порядку величины» (не уверен, что это правильный термин)).

То же самое применимо здесь, поэтому мы можем уменьшить O([n*log(n)] + n) до O(n*log(n)). Однако мы не можем уменьшить это до O(log(n)), так как это будет логарифмически, а это не так.

Answer 2

Если я правильно понял, вы спрашиваете о разнице между append и cons.

Время, используемое (cons a b), не зависит от значений a и b. Вызов выделяет некоторую память, тэги - тегом типа («пара») и сохраняет указатели на значения a и b в паре.

Сравните это с (append xs ys). Здесь append необходимо сделать новый список, состоящий из элементов как xs, так и ys. Это означает, что если xs является списком n элементов, то append необходимо выделить n новых пар для хранения элементов xs.

Вкратце: append необходимо скопировать элементы в xs и, таким образом, время пропорционально длине xs. Функция cons использует время независимо от того, с какими аргументами он вызывается.