Каково время поиска неупорядоченной карты в C ++ STL?

Question

У меня есть несколько 2D-массивов и есть некоторые соответствующие значения для каждого 2D-массива. Я конвертирую эти 2D-массивы в строки, а затем эти строки используются в качестве «ключей», а соответствующие значения 2D-массивов используются в качестве «значений» в неупорядоченной карте.

Процесс преобразования 2D-массива в строку (с примером):

A [3] [3] = {(1,2,3), (4,5,6), (7,8,9)}

Соответствующая строка будет иметь вид: 1 + 2 + 3 * 4 + 5 + 6 * 7 + 8 + 9

Так, каково будет время поиска ключа в таблице ha sh, которая внутренне используется неупорядоченным карта ?

Answer 1

Если ваш ключ - std::string, то для хеширования строки потребуется некоторое время. Стандартная библиотека Microsoft Visual C ++ плохо выполняет хеширование, но делает это за постоянное время O (1). GNU - другая крайность, использующая очень хорошее ха sh, и это будет O (K) по длине ключа. Таблица ha sh «время поиска ключа», как вы ее называете, будет амортизироваться O (1) по отношению к количеству элементов в таблице, но если другие строки хэшируются в том же сегменте, они должны быть сравнивается: каждое из этих сравнений будет O (1), если длины различаются, хотя и O (K) для соответствия. Это все здравый смысл, на самом деле, когда люди запутываются, пытаясь дать единственное значение big-O для всей операции: ну, в данном случае это O (K), так как это самая сложная сложность любой из задействованных операций. .