Вопрос по algorithm – Время сложности алгоритма

1

В настоящее время у меня возникают проблемы с определением и пониманием времени сложности следующего алгоритма.

Предыстория: существует список файлов, каждый из которых содержит список идентификаторов кандидатов. И количество файлов, и количество кандидатов в них не являются фиксированными.

Как бы вы рассчитали сложность времени для алгоритма, который отвечает за: Читать каждый файл и добавлять все уникальные идентификаторы кандидатов в Hashset?

Благодарю.

Error: User Rate Limit Exceeded Gareth McCaughan

Ваш Ответ

1   ответ
0

aba * b.

if the number of distinct candidates increases as we read more (so, for example, 90% of the files are always new candidates) then m is proportional to n. that means that the work of adding each candidate increases proportional to n. so the total work is proportional to n^2 (since for each candidate we do work proportional to n, and there are n candidates). so the worst case is O(n^2).

if the number of distinct candidates is actually fixed, then as you read more and more files they tend to be just full of known candidates. in that case the extra work for inserting into the set is constant (you only get the strange behaviour a fixed number of times for the unique candidates - it doesn't depend on n). in that case the performance of the set does not keep getting worse as n gets larger and larger, so the worst case complexity remains O(n).

Error: User Rate Limit Exceeded user1339335

Похожие вопросы