В выражении «Взвешенный алгоритм быстрого объединения следует не более lg N указателей, чтобы определить, связаны ли два из N объектов» что означает lg?
lg N обозначает логарифм N.В вычислениях принято использовать lg (в отличие от log) для явного обозначения логарифма с основанием-2, но это не универсально.
lg N
N
lg
log
Вы уверены, что ваш источник говорит "1g N"? Потому что для меня это больше похоже на «lg N» == «log N» ... Возможно, вы захотите прочитать структуру данных Disjoint-Set, особенно ту часть, которая содержит сжатие пути (всегда с прямым указателем на голову) и ранжирование (сохранение веса / размера / ранга набора). (http://en.wikipedia.org/wiki/Disjoint-set_data_structure)
Надеюсь, это поможет.