Какова временная сложность упорядоченных операций в TreeSet? - PullRequest
Новая
       16

Какова временная сложность упорядоченных операций в TreeSet?

5 голосов
/ 07 марта 2011

Какова временная сложность следующих операций в java.util.TreeSet?

  • first()
  • last()
  • lower()
  • higher()

Я бы предположил, что это постоянное время, но API не дает никаких гарантий.

Ответы [ 5 ]

11 голосов
/ 07 марта 2011

На самом деле, я бы подумал, что все эти операции будут O(logN) для общей реализации.

  • Чтобы first() и last() были O(1), реализация TreeSet должна поддерживать указатель на самый левый и самый правый конечные узлы в дереве соответственно. Их сохранение добавляет постоянные затраты на каждую вставку и, по крайней мере, постоянные затраты на каждое удаление. В действительности реализация, вероятно, найдет левый / правый узлы на лету ... что является операцией O(logN).

  • Методы lower() и higher() должны выполнять ту же работу, что и get, и поэтому являются O(logN).

Конечно, вы можете проверить исходный код самостоятельно, чтобы увидеть, что на самом деле происходит.

1 голос
/ 11 августа 2012

Похоже, что first () и last () будут O (log n), а не O (1) на основе Implentation (sun jdk 1.6.0_23) TreeMap, который используется TreeSet по умолчанию: 

 /**
 * Returns the first Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getFirstEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.left != null)
            p = p.left;
    return p;
}

/**
 * Returns the last Entry in the TreeMap (according to the TreeMap's
 * key-sort function).  Returns null if the TreeMap is empty.
 */
final Entry<K,V> getLastEntry() {
    Entry<K,V> p = root;
    if (p != null)
        while (p.right != null)
            p = p.right;
    return p;
}
0 голосов
/ 16 января 2015

Я на самом деле посмотрел исходный код, в http://developer.classpath.org/doc/java/util/TreeSet-source.html, first () вызывает maps.firstKey (), затем в http://developer.classpath.org/doc/java/util/TreeMap-source.html

393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )

и в firstNode () он выполняетцикл while для перехода влево 

952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )
0 голосов
/ 07 марта 2011

Это будет зависеть от реализации.Я не очень знаком с JAVA, но кажется, что все эти операции являются операциями обхода (получить наименьший элемент, получить наибольший элемент, получить следующий более высокий или следующий более низкий).

Если дерево реализовано как Самобалансирующееся дерево бинарного поиска , как AVL Tree или любой другой вид структуры сбалансированного дерева, вы будете смотреть на Average-Case и Worst-Case O(log n) время для каждой из операций и лучший вариант O (1).

0 голосов
/ 07 марта 2011

API не дает никаких гарантий, потому что они основаны на стандартной модели дерева. Наилучшим случаем является O (1), в среднем O (log n), а наихудшим O (n).

Из документации:

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

Это не те функции, которые вы просили, но подумайте о том, как Java будет проходить через TreeSet.

...