0
Для последовательного поиска, каково среднее количество сравнений, необходимых для поиска записи в файле?последовательный поиск
A
ответ
3
A sequential search начинается с начала файла и проверяет каждый элемент один за другим до тех пор, пока не будет найден нужный элемент. Предполагая, что запись, которую вы ищете, существует в файле ровно один раз и может быть где угодно в файле с равной вероятностью, среднее число сравнений равно половине количества записей в файле.
Однако, если запись не существует в файле, вам нужно будет изучить каждую запись в файле, прежде чем открывать ее.
1
Для списка с n элементами лучший случай - это когда значение равно первому элементу списка, и в этом случае требуется только одно сравнение. Наихудший случай - когда значение отсутствует в списке (или встречается только один раз в конце списка), и в этом случае необходимы n сравнений.
Asymptotically, следовательно, стоимость наихудшей и ожидаемая стоимость линейного поиска оба O (п)
0
Я хотел бы добавить несколько моментов, что предыдущие ответы не в состоянии указать на:
С другой стороны, мы должны рассмотреть, доступен ли файл на одном устройстве или распространяется на несколько устройств. В случае T-баров, тогда сложность будет
O(T*N/(1+log(T))).В целом, последовательный поиск принимает
O(N) time complexity.В сочетании с структурами данных, такими как R-Tree, он может обеспечить наилучшую временную сложность
O(N/(log(log(N))))в случае записей в файле.Это зависит от структуры/формата файла, так что если поля данных доступны на карте хэша, последовательный поиск - это отставание.
И наихудший случай всех записей, когда значения нет в файле. –
Я также видел его как (n + 1)/2. Почему n + 1? – neuromancer
@Phenom: Это потому, что вы можете начать с двух разных предположений. Если вы предполагаете, что знаете, что запись находится в файле, и вам просто нужно найти индекс, минимальное количество сравнений равно 1, а максимум (n-1) со средним значением ((n-1) + 1)/2 = n/2. Если вы предполагаете, что не знаете, что запись в файле, минимальное значение равно 1, максимальное значение равно n, и поэтому среднее значение (n + 1)/2 в том случае, если элемент находился в файле, а n если это не так. –