Вопрос по big-o, algorithm, hashset, time-complexity – Сложность времени для алгоритма
Я прав в своем объяснении при расчете временной сложности следующего алгоритма?
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. Это не домашняя работа, просто анализ алгоритма моей системы для оценки производительности.
file вmoduleMarksheetFilesпочему бы не вырваться из внутреннего цикла? Наконец, какая структура данныхmarksheetFiles?
Ted Hopp
Нет, это не квадрат, это O (nk). (Технически это означает, что этоalso O ((nk) & # xB2;), но нам все равно.)
Ваше заблуждение заключается в том, что здесь важнее всего производительность HashSet в худшем случае. Однако, хотя хеш-таблица может иметь время вставки O (n) в худшем случае (если нужно перефразировать каждый элемент), ееamortized время вставки равно O (1) (при условии, что ваша хеш-функция хорошо себя ведет;File.GetHashCode предположительно есть). Другими словами, если вы вставляете несколько вещей, так много из них будет O (1), что случайная вставка O (n) не имеет значения.
Следовательно, мы можем рассматривать вставки как операции с постоянным временем, поэтому производительность определяется только числом итераций в теле внутреннего цикла, которое равно O (nk).
hash(element)=1 [для каждого элемента] - каждый поискO(n)таким образомworst case Сложность всего алгоритма действительноO(n^2k^2), Средний случай, конечно, нет.
Похожие вопросы
