Я должен реализовать функцию итератора в Java для сбалансированного дерева, например дерева AVL с амортизированной сложностью O (1 + log (N/M)) и не уверен, что это значит? Любые ссылки или пояснения будут очень полезны. Спасибо.Амортизированная сложность для итераторов
Это означает, что для каждого последовательного вызова метода итератора next() сложность вызова метода будет уменьшаться. для дерева с N узлами первый вызов должен иметь сложность O (log (N)), следующий вызов должен иметь O (log (N/2)) и т. д. , чтобы действительно понять сложность, вы должны иметь некоторый фон в математике и информатике. для краткого и двусмысленного объяснения, см. here. для более глубокого понимания этой темы вы должны начать с Corman's Introduction to algorithms
Что такое N? Что такое M? Вам нужно описать, для чего нужны эти константы, чтобы мы могли вам помочь. – templatetypedef
Извинения, N - количество узлов в моем дереве. Значения i.e и M - количество узлов, которые я посетил в порядке возрастания .... – user1950055
(O (1 + log n) эквивалентно O (log n).) –