В моем коде Java TreeSet Итерация является доминирующим фактором времени. При взгляде на систему я считаю, что это O (n) сложность. Кто-нибудь может это подтвердить?Какова временная сложность итерации TreeSet?
Я имею в виду, что, предоставляя ссылки назад от дочернего узла к родительскому узлу я мог бы улучшить производительность.
TreeSet итерация, конечно, O (N), как можно ожидать от любого разумного алгоритма прохода по дереву.
Я имею в виду, что, предоставляя ссылки назад от дочернего узла к родительскому узлу я мог бы улучшить производительность.
TreeMap (который основан на TreeSet) уже имеет такие родительские ссылки. Это метод, все это сводится к тому:
private Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
Я думаю, что ключевым моментом является то, что не только узлы листьев имеют прикрепленные значения. Для 'n' leafs у вас есть« O (n log n) »узлы, но также значения« O (n log n) »). В реальных случаях я ожидал бы, что операции 'O (n)' доминируют над операциями O (n log n) '. –
Я думал, что это будет O (п) + O (LOGN), потому что если вы перебор в порядке, вы должны первое бревно использования (п) обходы, чтобы найти левые или правый лист, а затем у вас есть п обходы, чтобы ходить по дереву в обратном направлении. Таким образом, у вас есть O (n)? Имеет ли смысл моя математика? –
@john: O (n) + O (log n) - это то же, что и O (n) для определения. –
Рассматривали ли вы взять копию TreeSet, когда вы изменить его? Если властвуй времени тратится на TreeSet итерации (а не его модификации), а затем скопировать TreeSet в массив или ArrayList (только тогда, когда изменяется) и только итерация этого массива/ArrayList может почти elminate стоимость TreeSet итерации.
Или 'ImmutableSortedSet' Guava, который поддерживается массивом. –
Этот вопрос не имеет смысла. Похоже, вы говорите, что повторение вашего дерева - O (n). Это лучшее, что вы можете сделать для итерации. Для n элементов требуется время O (n). Если вы хотите ускорить выполнение кода, в котором доминирует итерация, вам нужно изменить алгоритм, чтобы он не выполнял итерацию - например, путем поиска в дереве по ключу (что было бы O (log n)) вместо. – babbageclunk