Какова временная сложность этого алгоритма? - PullRequest
Новая
       8

Какова временная сложность этого алгоритма?

0 голосов
/ 09 мая 2019

Добрый день, я пытаюсь улучшить свои способности с помощью Big-O, и я написал алгоритм Java для вывода дерева на консоль. 

public static void printTree(Tree tree){
    int height = getHeight(tree);
    int maxWidth = (int)Math.pow(2, height) - 1;
    HashMap<Coordinate, Integer> coordinates = getTreeCoordinates(tree, maxWidth/(int)Math.pow(2, 1) + 1, 1, maxWidth);
    printCoordinatesToConsole(coordinates, maxWidth, height);
}

static void printCoordinatesToConsole(HashMap<Coordinate, Integer> coordinates, int width, int height){
    for (int j = 1; j <= height; j++){
        for (int i = 1; i <= width; i++){
            if (coordinates.containsKey(new Coordinate(i, j)))
                System.out.print(coordinates.get(new Coordinate(i, j)));
            else
                System.out.print(' ');
        }
        System.out.print("n\n");
    }
}

static HashMap<Coordinate, Integer> getTreeCoordinates(Tree tree, int x, int y, int maxWidth){
    HashMap<Coordinate, Integer> result = new HashMap<>();
    result.put(new Coordinate(x, y), tree.data);
    if (tree.left == null && tree.right == null){
        return result;
    }
    else if (tree.left == null){
        result.putAll(getTreeCoordinates(tree.right, x+maxWidth/(int)Math.pow(2, y+1) + 1, y+1, maxWidth));
        return result;
    }
    else if (tree.right == null){
        result.putAll(getTreeCoordinates(tree.left, x-maxWidth/(int)Math.pow(2, y+1) - 1, y+1, maxWidth));
        return result;
    }
    else{
        result.putAll(getTreeCoordinates(tree.right, x+maxWidth/(int)Math.pow(2, y+1) + 1, y+1, maxWidth));
        result.putAll(getTreeCoordinates(tree.left, x-maxWidth/(int)Math.pow(2, y+1) - 1, y+1, maxWidth));
        return result;
    }
}

Насколько я могу судить, сложность будет зависеть от:

1. Высота дерева поиска O (n)

2. Распределение координат для всех элементов в хэш-карте O (n)

3.Печать координат на экране O (ширина * высота)

Теперь, поскольку width равен 2 ^ height, что в худшем случае будет n, означает ли это, что сложность по времени равна O (n * 2 ^ n)? Кроме того, если бы я проигнорировал печать (или если бы я должен был печатать непосредственно по координатам на консоли, а не перебирать всю ширину / высоту), сложность тогда была бы O (n)

Спасибо!

1 Ответ

1 голос
/ 09 мая 2019
  1. Нахождение высоты дерева O (n).

Если getHeight более или менее соответствует следующему, это будет O (n), где n - количество узлов в дереве: 

static int getHeight(Tree tree) {
    if (tree == null) {
        return 0;
    }

    return 1 + max(getHeight(tree.left, tree.right));
}
  1. Сохранение координат для всех элементов в хэш-карте O (getTreeCoordinates) = O (height * n) прямо сейчас, но может быть улучшено до O (n).

O (HashMap.putAll) технически зависит от реализации, но почти наверняка линейно по количеству элементов! Вместо использования HashMap.putAll вы можете передать HashMap рекурсивным вызовам, например ::

static HashMap<Coordinate, Integer> getTreeCoordinates(Tree tree, int x, int y, int maxWidth){
    HashMap<Coordinate, Integer> result = new HashMap<>();
    return getTreeCoordinatesImpl(tree, x, y, maxWidth, result);
}

static void getTreeCoordinatesImpl(Tree tree, int x, int y, int maxWidth, HashMap<Coordinate, Integer> result){
    result.put(new Coordinate(x, y), tree.data);
    if (tree.right != null){
        getTreeCoordinatesImpl(tree.right, x+maxWidth/(int)Math.pow(2, y+1) + 1, y+1, maxWidth, result);
    }
    if (tree.left != null){
        getTreeCoordinatesImpl(tree.left, x-maxWidth/(int)Math.pow(2, y+1) - 1, y+1, maxWidth, result);
    }
}
  1. Печать координат на экране - O (height * width). Это будет O (n), где n - число узлов дерева, если вы перебираете HashMap вместо всех (x, y) координат.

И O (HashMap.containsKey), и O (HashMap.get) равны 1 (постоянное время). Чтобы быть точным, они амортизируются постоянными во времени - в среднем они занимают постоянное время, но один прогон может быть линейным по количеству элементов хэш-карты в редком худшем случае.

В больших обозначениях O все константы эквивалентны (O (1) эквивалентно O (2)). Итак:

O (printCoordinatesToConsole) =

O (height) * O (width) * (O (HashMap.containsKey) + O (HashMap.get)) =

O (height) * O (width) * O (1) =

O (height * width)

Теперь, поскольку width равен 2 ^ height, что в худшем случае будет n, означает ли это, что сложность по времени равна O (n * 2 ^ n)?

Давайте посчитаем (n - количество узлов в дереве, я полагаю, getTreeCoordinates отредактировано, как описано выше):

O (printTree) =

O (getHeight) + O (getTreeCoordinates) + O (printCoordinatesToConsole) =

O (n) + O (n) + O (height * width)

С height * width> = n:

O (printTree) = O (height * width)

Кроме того, если бы я проигнорировал печать (или если бы я должен был печатать непосредственно с координатами на консоли, а не перебирать всю ширину / высоту), сложность была бы тогда O (n)

Да, тогда приведенное выше уравнение становится либо (без печати):

O (printTree) = O (getHeight) + O (getTreeCoordinates) = O (n) + O (n) = O (n)

или (печать с итерацией по хэш-карте узлов):

O (printTree) = O (getHeight) + O (getTreeCoordinates) + O (n) = O (n)

Будет полезно, если вы включите определения Tree, Coordinate и getHeight и, если применимо, содержимое tree. Вы также можете использовать онлайновую игровую площадку, например ideone.com , чтобы предоставить работоспособный пример.

...