Является ли временная сложность присвоения n значений массиву размером n O (n)?

Question

Я пытаюсь сопоставить индекс в Hashing для поиска элемента в массиве.Линейный поиск потребовал бы O (n) для поиска элемента в массиве размера n.В хешировании мы в основном уменьшаем временную сложность до O (1), создавая двумерную матрицу нулей (скажем, hash [1000] [2]) и переназначая hash [a [i]] [0] на 1, еслиa [i] положителен и хеш [-a [i]] [1], если a [i] отрицателен.Здесь a [i] - массив, из которого мы должны искать элемент.

    for(i=0 ;i<n    ;i++)
    {
        if(a[i]>=0)
            has[a[i]][0]=1;
        else
            has[-a[i]][1]=1;
    }

Сколько времени занимает выполнение приведенного выше кода?Даже с помощью хеширования, разве мы не имеем временную сложность O (n), как линейный поиск?Разве то, что потребовалось для присвоения n 1 в двумерном массиве нулей, равно времени, затрачиваемому на линейный поиск элемента?

Answer 1

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

Вы можете поддерживать порядок сортировки, используя тот же двоичный поиск для вставки новых элементов, что и для поиска существующих элементов.

Этот последний пункт важен: как отмечено в комментариях, сортировка перед каждым поиском ухудшает время поиска до точки, в которой линейный поиск методом грубой силы быстрее для небольших наборов данных. Но эти накладные расходы могут быть устранены; массив никогда не нужно сортировать , если вы сохраняете порядок сортировки при вставке новых элементов.