Прав ли я в своем объяснении при расчете временной сложности следующего алгоритма?
HashSet, moduleMarksheetFiles, используется для добавления файлов, содержащих указанное имя модуля.
for (File file: marksheetFiles){ while(csvReader.readRecord()){ String moduleName = csvReader.get(ModuleName); if (moduleName.equals(module)){ moduleMarksheetFiles.add(file); } } }
Пусть m будет количеством файлов
- Пусть k будет средним числом записей в файле.
- Поскольку каждый файл добавляется только один раз, поскольку HashSet не допускает дублирования. HashSet.add() в среднем составляет O(1) и O(n) в худшем случае.
- Поиск записи с указанным именем модуля включает в себя сравнение каждой записи в файле с именем модуля, для чего потребуется O(n) шагов.
Следовательно, средняя временная сложность будет: O((m*k)^2).
Это верно?
Кроме того, как бы вы рассчитали худший случай?
Спасибо.
PS. Это не домашнее задание, просто анализ алгоритма моей системы для оценки производительности.
file
кmoduleMarksheetFiles
, почему бы не выйти из внутреннего цикла? Наконец, что за структура данныхmarksheetFiles
? - person Ted Hopp   schedule 29.04.2012