Читать «Фундаментальные алгоритмы и структуры данных в Delphi» онлайн - страница 14

Быстродействие первого алгоритма = k1 * (n + 100000)

Быстродействие второго алгоритма = k2* n(^2^)

Пусть константы kl и k2 сравнимы по величине. Какой алгоритм лучше использовать? Если следовать О-нотации, то предпочтительнее будет первый алгоритм, поскольку он принадлежит к классу О(n). Тем не менее, если известно, что значение n в реальных условиях не будет превышать 100, более эффективным окажется второй алгоритм.

Таким образом, алгоритм нужно выбирать и с учетом его назначения - не только на основании О-нотации, но принимая во внимание время выполнения при средних значениях количества элементов (или, если угодно, условий использования), на которых алгоритм будет применяться. Следовательно, выбор алгоритма должен осуществляться только на основе измерения профилировщиком времени выполнения вашего приложения для ваших данных. Не полагайтесь ни на какие книги (в том числе и на эту), верьте только измеренному времени.

Лучший, средний и худший случаи

Помимо всего прочего, необходимо рассмотреть еще один вопрос. О-нотация относится к среднему случаю. Вернемся к нашим экспериментам, связанным с поиском элемента в массиве. Если бы фамилия "Smith" всегда была первым элементом в массиве, последовательный поиск был бы быстрее бинарного, - искомый элемент был бы обнаружен при первом же выполнении цикла. Такая ситуация известна под названием лучший случай. Для нашего примера в О-нотации ее можно представить как O(1) (т.е. выполнение алгоритма занимает одно и то же время независимо от количества элементов в массиве).

Если бы фамилия "Smith" всегда была последним элементом в массиве, последовательный поиск был бы очень медленным. Такая ситуация известна под названием худший случай. В нашем примере ее можно представить как О(n), точно так же, как и для среднего случая.

Несмотря на то что для бинарного поиска быстродействие в лучшем случае (искомый элемент всегда находится в средине массива) равно быстродействию в лучшем случае для последовательного поиска, тем не менее, его быстродействие в худшем случае намного выше. Собранные нами статистические данные при поиске элемента, которого нет в массиве, являются значениями для худшего случая.

В общем, при выборе алгоритма следует учитывать значения в О-нотации для среднего и худшего случаев. Лучшие случаи, как правило, не интересны, поскольку программисты всегда более обеспокоены "граничными" условиями, по которым и будут судить о быстродействии приложения.

Таким образом, мы увидели, что О-нотация - очень ценное средство оценки быстродействия различных алгоритмов. Кроме того, следует помнить, что О-нотация в общем случае имеет смысл только для больших n. Для небольших n выбор алгоритма лучше осуществлять на основе статистических данных о времени его выполнения. Единственным достоверным методом оценки эффективности алгоритма является определение времени его работы. Поэтому не гадайте, а интенсивно используйте профилировщик.