Временная сложность алгоритма

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

  • 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. Это не домашнее задание, просто анализ алгоритма моей системы для оценки производительности.


person user1339335    schedule 29.04.2012    source источник
comment
В ваших 4-м и 5-м пунктах n == m? Кроме того, как только вы добавите file к moduleMarksheetFiles, почему бы не выйти из внутреннего цикла? Наконец, что за структура данных marksheetFiles?   -  person Ted Hopp    schedule 29.04.2012
comment
Разве это не просто О (мк)? Как вы думаете, почему он в квадрате?   -  person Kevin    schedule 29.04.2012
comment
@Ted Hopp -marksheetFiles также является структурой данных HashSet. Да, n==m в 5-м пункте, извините. Поскольку система уже разработана, в настоящее время невозможно добавить перерыв до следующего цикла. Хотя спасибо за совет   -  person user1339335    schedule 29.04.2012
comment
@Kevin - я думал, что это в квадрате, потому что вам придется сравнивать каждую запись с именем модуля. Является неправильным. Не могли бы вы объяснить, почему вы думаете, что это O (mk)?   -  person user1339335    schedule 29.04.2012
comment
если moduleName.equals(module) не занимает O (mk) времени, общая временная сложность составляет O (mk).   -  person deebee    schedule 29.04.2012
comment
в худшем случае каждое добавление к хэш-набору будет занимать время O(mk). Таким образом, сложность будет O((mk)^2)   -  person deebee    schedule 29.04.2012
comment
@debee - Не могли бы вы рассказать об этом подробнее?   -  person user1339335    schedule 29.04.2012
comment
Учитывая, что moduleName.equals(module) равен O(1), а avg hashset.add равен O(1), цикл занимает время O(mk). Если hashset.add занимает O(mk) времени в худшем случае, то легко увидеть, что общая временная сложность равна O((mk)^2). Но, глядя на код, hashset содержит только имена файлов, а файлов всего m, поэтому, чтобы исправить мое предыдущее утверждение, это будет O (m ^ 2 * k)   -  person deebee    schedule 29.04.2012
comment
возможный дубликат время сложности алгоритма   -  person amit    schedule 29.04.2012


Ответы (1)


Нет, это не в квадрате, это O(nk). (Технически это означает, что это тоже O((nk)²), но нам все равно.)

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

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

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