Удалось ли мне правильно оценить O (n)?

Question

Обратите внимание: этот вопрос не о лучшей реализации алгоритма и не о структурах данных.

---

Учитывая двоичное дерево, необходимо убедиться, что это bst. Я знаю о гораздо более эффективном (O(n)) алгоритме, вопрос не об этом. Я практикую свои навыки большой оценки:

int isBST(struct node* node)  
{  
  if (node == NULL)  
    return(true);  

  if (node->left!=NULL && maxValue(node->left) > node->data)  
    return(false);  

  if (node->right!=NULL && minValue(node->right) < node->data)  
    return(false);  

  if (!isBST(node->left) || !isBST(node->right))  
    return(false);  

  return(true);  
}

.. при условии, что maxValue(...)/minValue(...) являются вспомогательными функциями, для выполнения каждой из которых требуется O(n).

Если h - это количество «уровней», которое начинается с корня и заканчивается листьями. На каждом уровне maxValue(...) и minValue(...) вызываются в диапазоне (n - 1) / 2^l, где l - текущий уровень. Есть h уровней, поэтому я ожидаю получить что-то вроде (n - 1) / 1 + (n - 1) / 2 + (n - 1) / 4 + ... + (n - 1) / 2^h. Так что, похоже, O(n * h) - это правильная верхняя граница, не так ли?

Пожалуйста, проверьте мой способ мышления.

Answer 1

Да, вы правы.Это правильная верхняя граница.На каждом уровне вы будете выполнять всю работу O (n) для maxValues.Вы можете проверить this для очень похожего анализа во время выполнения (он дает O (nlogn), поскольку h = logn, поскольку предполагается, что он хорошо сбалансирован).Использование h - хороший вызов, если дерево полностью разбалансировано (h = O (n)), тогда время выполнения будет O (n ^ 2), но если оно идеально сбалансировано (h = O (logn)), у вас будет O(nlogn).

Еще одна вещь, вы можете фактически кэшировать / вычислять значения max / min во время рекурсии, это даст вам амортизированное время выполнения O (n):

struct helper {
  int min;
  int max;
};

int isBST(struct node* root) {  
  struct helper help;
  return isBST_internal(root, &help);  
}

int isBST_internal(struct node* root, struct helper *min_max) {
  if (!root) return true;

  if (root->left) {
    // Recurse on left
    struct helper left_helper;
    int is_left_BST = isBST_internal(root->left, &left_helper)

    if (!is_left_BST || left_helper.max > root->data)
      return false;

    min_max->min = left_helper.min;
  } else {
    // If no left subtree, the min value should be the current node value
    min_max->min = root->data;
  }

  if (root->right) {
    // recurse on right side
    struct helper right_helper;
    int is_right_BST = isBST_internal(root->right, &right_helper)

    if (!is_right_BST || right_helper.min < root->data)
      return false;

    min_max->max = left_helper.max;
  } else {
    // If no right subtree, the max value should be the current node value
    min_max->max = root->data;
  }

  // If we have not returned yet it means all conditions for BST are satisfied
  // Also, min_max is properly set now.

  return true
}

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