Метод медленнее после запоминания

Question

Я работаю над следующей проблемой алгоритма на Leetcode:

Учитывая бинарное дерево, определить, является ли высота сбалансирована. Для этой проблемы, высота сбалансирован бинарное дерево определяется как бинарное дерево в не которой глубина двух поддеревьев каждого узла и не отличаются более , чем 1.

Вот ссылка: https://leetcode.com/problems/balanced-binary-tree/

Я написал два решения - оба из которых проходят тесты Leetcode. Первый должен быть более дорогим, чем второй, поскольку он многократно проверяет узлы каждого поддерева для вычисления высот для каждого узла. Второе решение должно собирать все высоты узлов в кеш, чтобы вычисление не повторялось. Однако, оказывается, мое второе решение на самом деле медленнее первого, и я понятия не имею, почему. Любой вход?

Решение 1:

def is_balanced(root) #runs at 139 ms 
    return true if root.nil? 
    left_height = height(root.left) 
    right_height = height(root.right) 

    if !equal?(left_height, right_height) 
    return false 
    else 
    is_balanced(root.left) && is_balanced(root.right) 
    end 
end 

def height(node) 
    return 0 if node.nil? 
    [height(node.left), height(node.right)].max + 1 
end 

def equal?(num1, num2) 
    return true if (num1-num2).abs <= 1 
    false  
end 

Решение 2: (отредактированное включить предложение cobaltsoda в)

@memo = {} 
def is_balanced(root) 
    @memo = {} 
    return true if root.nil? 
    left_height = height(root.left) 
    right_height = height(root.right) 

    if !equal?(left_height, right_height) 
    return false 
    else 
    is_balanced(root.left) && is_balanced(root.right) 
    end 
end 

def height(node) 
    @memo[node] = 0 if node.nil? 
    @memo[node] ||= [height(node.left), height(node.right)].max + 1 
end 

def equal?(num1, num2) 
    return true if (num1-num2).abs <= 1 
    false  
end 

Поскольку второе решение использует запоминание, она не должно вырезать избыточность и снизить время расходы программы? Не уверен, что мне не хватает.

Также, с мемуатикой это происходит от алгоритма O (NlogN) до O (N) правильно?

Answer 1

Это ближайший вы получите к оригинальному алгоритму с кэшированием:

def height(node) 
    return 0 if node.nil? 
    @memo[node] ||= [height(node.left), height(node.right)].max + 1 
end 

Оператор ||= здесь работает равносильно @memo[node] || @memo[node] = [height(node.left), height(node.right)].max + 1.

Вы должны учитывать, что назначение хэша @memo требует дополнительного (хотя и очень небольшого количества) времени, поэтому, возможно, не стоит использовать кеширование для небольших двоичных деревьев.