Блог

В https://www.techiedelight.com/print-all-paths-from-root-to-leaf-nodes-binary-tree/, код для печати с корня на лист для каждого конечного узла приведен ниже.

Они утверждают, что алгоритм O(n), но я думаю, что он должен быть O(n log n), где n-количество узлов. Стандартный DFS обычно равен O(n E), но печать путей, похоже, добавляет журнал n. Предположим, что h-высота идеального бинарного дерева. На последнем уровне есть n/2 узла, следовательно, n/2 пути, которые нам нужно распечатать. Каждый путь имеет h 1 (давайте просто скажем, что это h для математической простоты) узлов. Поэтому нам нужно в конечном итоге напечатать узлы h * n/2 при печати всех путей. Мы знаем, что h = log2(n). Итак, h * n/2 = O(n log n)?

Является ли их ответ неправильным, или здесь что-то не так с моим анализом?

 #include <iostream>
#include <vector>
using namespace std;
 
// Data structure to store a binary tree node
struct Node
{
    int data;
    Node *left, *right;
 
    Node(int data)
    {
        this->data = data;
        this->left = this->right = nullptr;
    }
};
 
// Function to check if a given node is a leaf node or not
bool isLeaf(Node* node) {
    return (node->left == nullptr amp;amp; node->right == nullptr);
}
 
// Recursive function to find paths from the root node to every leaf node
void printRootToleafPaths(Node* node, vector<int> amp;path)
{
    // base case
    if (node == nullptr) {
        return;
    }
 
    // include the current node to the path
    path.push_back(node->data);
 
    // if a leaf node is found, print the path
    if (isLeaf(node))
    {
        for (int data: path) {
            cout << data << " ";
        }
        cout << endl;
    }
 
    // recur for the left and right subtree
    printRootToleafPaths(node->left, path);
    printRootToleafPaths(node->right, path);
 
    // backtrack: remove the current node after the left, and right subtree are done
    path.pop_back();
}
 
// The main function to print paths from the root node to every leaf node
void printRootToleafPaths(Node* node)
{
    // vector to store root-to-leaf path
    vector<int> path;
 
    printRootToleafPaths(node, path);
}
 
int main()
{
    /* Construct the following tree
              1
            /   
           /     
          2       3
         /      / 
        4   5   6   7
               /     
              8       9
    */
 
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->right->left->left = new Node(8);
    root->right->right->right = new Node(9);
 
    // print all root-to-leaf paths
    printRootToleafPaths(root);
 
    return 0;
}
 

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

Временная сложность «напечатать один путь» равна O(log n). Чтобы напечатать все пути (n/2 листа), требуется O( n log n )

Затем вам нужно сравнить стоимость обхода узла и стоимость пути печати. Я верю, что в большинстве современных ОС стоимость печати намного превышает стоимость обхода узла.

Таким образом, фактическая временная сложность равна O(n log n) ( для печати ).

Я предполагаю, что веб-сайт может игнорировать стоимость печати, поэтому он утверждает, что сложность во времени составляет O(n).

Сложность составляет O(n log n) для сбалансированного двоичного дерева, но для произвольного двоичного дерева наихудший случай-O(n ²).

Рассмотрим дерево, состоящее из:

1. n/2 узлов в связанном списке на указателях их правого ребенка; и
2. В конце этого n/2 узла расположены в дереве с n/4 листьями.

Поскольку все листья n/4 имеют глубину более n/2 узлов, общее количество узлов во всех путях превышает n ^2/8, и это O(n ²)

Алгоритм проходит через O(n) узлов. Общее количество выполняемых им отпечатков равно O(n lg n) для сбалансированного дерева или O(n^2) для произвольного дерева.

Это зависит от того, во что обошлись операции.

Например, сохранение или увеличение n-разрядного числа или указателя часто рассматривается как операция O(1). На любом физическом компьютере, если у вас 2^100 узлов, вам понадобятся разрядные указатели lg(2^100) (или имена узлов), для копирования которых потребуется больше времени, чем для 64 или 32-разрядных имен узлов. В определенном смысле копирование указателя должно занять O(lg n) времени!

Но нам все равно. Мы неявно устанавливаем цену операций и указываем затраты в терминах этих операций.

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

То же самое происходит в спецификации алгоритмов библиотеки std; это гарантирует максимальное количество вызовов предиката.