В худшем случае анализ сложности функции двоичного дерева «уходит»

Question

Интересно, корректен ли мой анализ сложности (T худший случай для n элементов / узлов) для следующих функций, оставленных в Haskell (Примечание: wurzel = root; C = постоянный коэффициент)

--abstract data type for bin trees

data Bintree el = Empty
                  | Node {left :: Bintree el, root :: el, right :: Bintree el} 
                    deriving Show

--extract all leaves of a given Bintree (output: list)

leaves :: Bintree el -> [el]
leaves Empty = []
leaves (Node Empty root Empty) = [root]
leaves (Node left root right) = leaves left ++ leaves right

Answer 1

Нет, ошибок много.Вот некоторые из наиболее ярких:

• Когда вы пишете T(n/2)+T(n/2)+T(n/4)+T(n/4)+..., вы, похоже, предполагаете, что половина узлов находится в левой ветви, а половина - в правой.Это не всегда верно - некоторые деревья сбалансированы, но некоторые, конечно, нет.
• Даже если дерево сбалансировано, существует не только 2 поддерева размера n / 4 - их 4. Аналогично, есть8 поддеревьев размера n / 8, а не 2.
• Правильное выражение для описания «деления n на 2 i раз» равно n/(2^i), а не n/(i^2).Кроме того, несмотря на вышеприведенный комментарий о балансировке, вы хотели бы продолжать деление до тех пор, пока не достигнете только одного листа, поэтому правильный базовый случай многоточия - T(n/n), а не один из T(n/(2^n)) или T(n/(n^2)).
• Если вы несколько раз разделите на два и добавите результаты, как в n + n/2 + n/4 + n/8 + n/16 + ..., навсегда, вы получите 2*n, а не log_2(n).
• В любом случае, это не относится, потому что выне добавляются кратные n.T(n) + T(n/2) + T(n/4) + T(n/8) + T(n/16) + ... не обязательно каким-либо особым образом относится к T(2*n) (или T(log_2(n))).Например, представьте, если f(n) = 1.Тогда сумма f(1) + f(1/2) + f(1/4) + f(1/8) + f(1/16) + ... = 1 + 1 + 1 + 1 + 1 + ... расходится, хотя f(1 + 1/2 + 1/4 + 1/8 + 1/16 + ...) = f(2) = 1.