Не могли бы вы помочь мне рассчитать сложность Big-O? - PullRequest
Новая
       41

Не могли бы вы помочь мне рассчитать сложность Big-O?

0 голосов
/ 15 марта 2019

Недавно я реализовал телефонную книгу с помощью Tree структуры данных.

Я ищу не только рабочее решение, но и оптимальное решение с точки зрения времени выполнения и хранения.

Из моих вычислений требуется от N*log(T) до add() и get(), где N - это число входных символов, а T - это число дочерних элементов каждого узла.

Я могу объяснить свои мысли: когда вставляется новое имя, тогда требуется время, чтобы найти Node с тем же самым символом в дочерних элементах TreeMap = log(T), и это происходит N раз для каждого символа в аргументе String.

Я прав? 

public final class PhoneBook {

private final Node name;

private final Node surname;

private final Comparator<Record> comparator;

public PhoneBook() {
    this.name = new Node();
    this.surname = new Node();
    comparator = (r1, r2) -> {
        int result = r1.getName().compareTo(r2.getName());
        if (result == 0) {
            result = r1.getSurname().compareTo(r2.getSurname());
            if (result == 0) {
                result = r1.getNumber().compareTo(r2.getNumber());
            }
        }
        return result;
    };
}

public void add(final Record record) {
    add(record.getName().toLowerCase(), record, name);
    add(record.getSurname().toLowerCase(), record, surname);
}

public SortedSet<Record> get(final String prefix) {
    final String lc = prefix.toLowerCase();
    final List<Record> recordsRetrievedByName = get(lc, name);
    final List<Record> recordsRetrievedBySurname = get(lc, surname);
    final SortedSet<Record> result = new TreeSet<>(comparator);
    result.addAll(recordsRetrievedByName);
    result.addAll(recordsRetrievedBySurname);
    return result;
}

private List<Record> get(final String prefix, final Node ancestor) {
    Node node = ancestor;
    for (final char c: prefix.toCharArray()) {
        final Node child = node.children.get(c);
        if (child == null) {
            return Collections.emptyList();
        }
        node = child;
    }
    return node.records;
}

private void add(final String str, final Record record, final Node ancestor) {
    Node node = ancestor;
    for (final char c: str.toCharArray()) {
        final Node child;
        if (node.children.containsKey(c)) {
            child = node.children.get(c);
        } else {
            child = new Node();
            node.children.put(c, child);
        }
        child.records.add(record);
        node = child;
    }
}

private static final class Node {

    private final Map<Character, Node> children = new TreeMap<>();

    private final List<Record> records = new ArrayList<>();

}

}

И Record неизменный объект 

public final class Record {

private final String name;

private final String surname;

private final String number;

//constructor, getters, toString
}
...