Правильный способ анализа этого простого алгоритма

Question

Учитывая некоторые строки, ab, abc, ad, ace, ddd ... из файла, чтобы узнать, есть ли строка строк в строках. Если я хочу использовать хэш, чтобы проверить существование S.

Анализ алгоритмов: поскольку каждая операция «put» принимает O (1) * K время, где K - длина строки, создание отображение принимает O (n * K) время, где n - число строк. И поиск занимает постоянное время, поэтому общее время O (n * k). Правильно ли это? Хотя мы часто говорим, что хеш-таблица позволяет постоянно смотреть вверх, она обычно игнорирует время, затрачиваемое на создание хэша. Отвечая на такой вопрос, могу ли я сказать, что временная сложность O (n * k) или просто O (n)? Большое спасибо. Просто начал изучать алгоритм анализа.

String line = null; 

BufferedReader br = new BufferedReader(new File("file.txt")); 
HashMap<String, Integer> strs = new HashMap<String,Integer>(); 
while((line=br.readLine()) != null){ 
    Integer count = strs.get(line); 
    if(count == null){ 
     strs.put(line, 1); 
    } 
    count++; 
} 

// Suppose the string to be checked is "str"; 
if(strs.contains(str)){ 
    return true; 
} 
return false;  

Answer 1

Когда вы говорите O (n), n пропорционально размеру ввода. Однако вы спрашиваете, следует ли указывать O (n * k), где k также пропорционально размеру ввода. В этом случае то, что вы на самом деле говорите, это O (n^2) - где алгоритм может занять время t для ввода K, но для ввода 2k потребуется время 4t. Это вы хотите сказать?

Если вы просто хотите сказать, что для алгоритма требуется время t для ввода k, а время 2t для входа 2k, то вы просто говорите, что алгоритм O (n).

Теперь о алгоритме ... если я правильно его интерпретирую, шаги строят хеш при чтении файла, а затем поиск в хэш-таблице. Один проход над файлом - O (n) одновременно с помещением всех строк в хэш-таблицу, которая также является O (n) (при условии, что хэш-таблица достаточно хорошо реализована). Поиск одной записи в хеш-таблице - O (1).

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