Вопрос по big-o, algorithm, hashset, time-complexity – Сложность времени для алгоритма

1

Я прав в своем объяснении при расчете временной сложности следующего алгоритма?

A HashSet, moduleMarksheetFiles, is being used to add the files that contain the moduleName specified.

<code>for (File file: marksheetFiles){
     while(csvReader.readRecord()){
         String moduleName = csvReader.get(ModuleName);

         if (moduleName.equals(module)){
               moduleMarksheetFiles.add(file);
         }
     }
 }
</code>

Let m be the number of files

Let k be the average number of records per file. As each file is added only once because HashSet does not allow for duplicates. HashSet.add() is O(1) on average and O(n) for worst case. Searching for a record with the specified moduleName involves comparing every record in the file to the moduleName, will take O(n) steps.

Следовательно, средняя сложность по времени будет: O ((m * k) ^ 2).

Это правильно?

Кроме того, как бы вы рассчитали наихудший случай?

Благодарю.

PS. Это не домашняя работа, просто анализ алгоритма моей системы для оценки производительности.

если moduleName.equals (module) не займет O (mk) времени, общая сложность времени будет O (mk). deebee
@Ted Hopp -marksheetFiles также является структурой данных HashSet. Да, п == м в 5-м пункте извините. Поскольку система уже разработана, добавить разрыв в настоящее время невозможно до следующего цикла. Спасибо за совет, хотя user1339335
@Kevin - Я думал, что это квадрат, потому что вам придется сравнивать каждую запись с moduleName. Это неверно. Не могли бы вы объяснить, почему вы думаете, что это O (MK)? user1339335
В 4-й и 5-й пулях n == m? Кроме того, как только вы добавитеfile вmoduleMarksheetFilesпочему бы не вырваться из внутреннего цикла? Наконец, какая структура данныхmarksheetFiles? Ted Hopp
Разве это не просто O (MK)? Почему вы думаете, что это в квадрате? Kevin

Ваш Ответ

1   ответ
2

Нет, это не квадрат, это O (nk). (Технически это означает, что этоalso O ((nk) & # xB2;), но нам все равно.)

Ваше заблуждение заключается в том, что здесь важнее всего производительность HashSet в худшем случае. Однако, хотя хеш-таблица может иметь время вставки O (n) в худшем случае (если нужно перефразировать каждый элемент), ееamortized время вставки равно O (1) (при условии, что ваша хеш-функция хорошо себя ведет;File.GetHashCode предположительно есть). Другими словами, если вы вставляете несколько вещей, так много из них будет O (1), что случайная вставка O (n) не имеет значения.

Следовательно, мы можем рассматривать вставки как операции с постоянным временем, поэтому производительность определяется только числом итераций в теле внутреннего цикла, которое равно O (nk).

Как я уже сказал, это вводит в заблуждение - не неправильно. Цель понятна для опытных читателей - но может запутать начинающих программистов.
О (nk) означает, что оно линейно? user1339335
Линейный по произведению количество файлов и среднее количество строк на файл, да. Или, другими словами, линейно по общему количеству строк во всех файлах.
Правильно, да, я предполагаю, что хеш-функция хорошо работает.Fileиз стандартной библиотеки, предположительно, имеет.
Ваше последнее утверждение вводит в заблуждение. Вставка HashSet является O (nk) худшим случаем, даже с таблицей бесконечных размеров, которую не нужно перефразировать из-за коллизий. предполагатьhash(element)=1 [для каждого элемента] - каждый поискO(n)таким образомworst case Сложность всего алгоритма действительноO(n^2k^2), Средний случай, конечно, нет.

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