#algorithm #time-complexity #big-o #hashtable #clrs
Вопрос:
Как указано в книге CLR,на странице 260,
У меня не было бы никаких проблем, если бы автор сказал, что граница в конечном итоге
или даже
Какие теории мы будем применять, чтобы упростить исходный результат, т. е. отменить коэффициент 1/n a? Поскольку n является одним из входов функции, необходимо ли отменять ее, рассматривая как константу? Что я пропустил? есть ли у кого-нибудь такая же путаница T_T?
Ответ №1:
alpha/n является асимптотически меньшим (имеет более низкий порядок) по сравнению с alpha , поэтому его можно игнорировать. Когда n (размер хэш — таблицы, AFAIU) становится больше, 1/n значение стремится к нулю.
Примечание-таблица wiki не содержит 1/n функции, поскольку она оценивается как имеющая нулевое влияние
Аналогичная ситуация — если время есть Theta(n^2 100*n 10000) , доминирующее слагаемое квадратично, и
Theta(n^2 100*n 10000)` = Theta(n^2)