Скажем, у меня есть два массива одинаковой длины, один из типов x и другой типа y, причем x составляет половину размера в памяти y. Если я сгенерировал 2 объекта, один из типов x и другого типа y, и проверил, чтобы их соответствующие массивы содержали их, обе операции в среднем выполнялись бы в одно и то же время?
Можно ли улучшить это время с помощью другой (упорядоченной) структуры данных?array.contains runtime в терминах размера массива типа
Мой системы профессор ответил на этот:
Если время работы ограничено по числу команд, то исчерпывающие поиски на двух массивах дают равное время.
Если время работы ограничено скоростью доступа к памяти, тогда поиск по большему массиву (здесь «больше» означает больше байтов) занимает больше времени.
Независимо от того, может ли рабочее время быть привязанным к инструкциям или ограничено доступом к памяти, может зависеть от компилятора. Плохой компилятор может создавать множество инструкций, так что время связано с инструкциями.
Поиск определенного элемента в неупорядоченном массиве имеет сложность O(n), что означает, что он линейно зависит от количества элементов. Это не зависит от размера элемента, так как массивы имеют постоянное время произвольного доступа (адрес n-го элемента в массиве может быть рассчитан с использованием простой арифметики указателя).
Так что да, в поисках двух объектов потребуется в среднем одно и то же время. А точнее - имеют одинаковую сложность (линейную).
Поиск по упорядоченной структуре данных, такой как отсортированный список или двоичное дерево, позволяет использовать алгоритм O(log (n)) (бинарный поиск), который в среднем намного быстрее.
См. this cheatsheet, чтобы увидеть некоторые общие структуры данных и сложности выполняемых на них операций.
использование хэш-стол/хэш-набор. ожидаемый или оцененный поиск - O(1) Предполагая, что сравнение двух объектов - O(1).
, но в общем случае, для более крупного объекта 2x требуется больше времени для сравнения. однако это не влияет на массив время поиска, потому что во время этой операции можно использовать индекс, а не сам объект
В моем случае использования данные в нем должны быть заказаны. Но вторая часть вашего ответа эквивалентна тому, что я просил, спасибо! – Timestretch
К сожалению для этого приложения мне необходимо иметь упорядоченное (не упорядоченное в смысле, что данные растут или уменьшаются, но в том смысле, что данные находятся в определенном порядке и ДОЛЖНЫ оставаться в этом порядке) структура данных , Например, у меня есть один большой массив и один небольшой массив, и я хочу посмотреть, содержится ли меньший в более крупном в том же порядке. Я знаю сложность поиска по различным структурам данных, мне хотелось знать сложность сравнения двух объектов в памяти. – Timestretch