История изменений
Исправление alysnix, (текущая версия) :
Я так понял (возможно неверно), комплексити моего решения O(nlogn).
n log n - это только вставка в мапу. сложность вставки - log n, элементов - n.
то, что обход мепа(а он вовсе не обязан такое свойство давать эффективно) это сложность N, еще надо показать. если там просто дерево, то там будет беготня по поддеревьям, и сложность будет опять порядка n*log n
Исходная версия alysnix, :
Я так понял (возможно неверно), комплексити моего решения O(nlogn).
n log n - это только вставка в мапу. сложность вставки - log n, элементов - n.