Количество нет.слов в O (n)

Question

Я здесь на собеседовании. Еще один вопрос интервью, с которым у меня возникли трудности.

«Роза - это роза - это роза» алгоритм, который печатает количество раз встречается символ / слово. Например. A - 3 розы - 3 Is - 2

Также убедитесь, что при печати результаты, они в порядке что присутствовало в оригинале предложение. Все это в порядке n .

Я получил решение подсчитать количество вхождений каждого слова в предложении в том порядке, в котором оно присутствует в исходном предложении. Я использовал Dictionary<string,int>, чтобы сделать это. Однако я не понял, что подразумевается под порядком n. Это то, что мне нужно объяснение от вас, ребята.

Answer 1

Есть 26 символов, так что вы можете использовать counting sort для их сортировки, в вашей сортировочной таблице вы можете иметь индекс, который определяет, когда конкретный символ был посещен в первый раз, чтобы сохранить порядок вхождения. [Они могут быть отсортированы по их количеству и их появлению с сортировкой по типу radix].

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

Answer 2

Один из возможных способов - линейный обход строки. Затем создайте хэш и список. Идея состоит в том, чтобы использовать слово в качестве хэш-ключа и увеличивать значение для каждого вхождения. Если значение в хэше отсутствует, добавьте слово в конец списка. Пройдя через строку, просмотрите список по порядку, используя хеш-значения в качестве счетчика.

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

Answer 3

«Order n» относится к Big O нотации .Big O - это способ для математиков и компьютерщиков описать поведение функции.Когда кто-то указывает поиск строки «в порядке n», это означает, что время, необходимое для выполнения функции, растет линейно по мере увеличения длины этой строки.Другими словами, если вы нанесете график времени выполнения в зависимости от длины ввода, вы увидите прямую линию.

Сказать, что ваша функция должна иметь порядок n, не означает, что ваша функция должна равняться O (n), функция с большим O, меньшим O (n), также будет считаться приемлемой.В вашем случае проблем это было бы невозможно (потому что для подсчета буквы вы должны «коснуться» этой буквы, поэтому должна быть какая-то операция, зависящая от размера ввода).

Answer 4

Это ссылка на Big O нотация .По сути, интервьюер означает, что вы должны выполнить задачу с помощью алгоритма O (N).

Answer 5

Порядок N относится к анализу сложности вычислений Big O, где вы получаете хорошую верхнюю границу для алгоритмов. Это теория, которую мы рассматриваем на ранних этапах обучения в классе Data Structures, поэтому мы можем мучить, я имею в виду, помочь учащемуся получить возможность использовать ее, поскольку мы проходим сбалансированно, кучи разных деревьев знаний, все разные. В вашем случае они хотят, чтобы ваш алгоритм увеличивался за время вычислений пропорционально размеру текста по мере его роста.

Answer 6

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