время выполнения в лучшем случае означает, что у вас есть алгоритм, решающий проблему, и в лучшем случае этот алгоритм имеет особую сложность по времени.
Например, время выполнения в лучшем случае для сортировки выбора O (n 2 ), потому что он всегда будет выполнять столько операций, чем бы ни был массив. С другой стороны, наилучшим временем выполнения для сортировки вставкой является O (n), если входной массив уже отсортирован.
Наилучшее возможное время выполнения - это Концепция, насколько я знаю, представлена в книге Гейл Лакманн МакДауэлл Раскрытие Интервью кодирования *1014**1015*. Это означает, что у вас есть проблема, и вы пытаетесь оценить, насколько эффективно она может быть решена; у вас еще нет алгоритма, или если у вас есть алгоритм, то вы не знаете, существует ли другой алгоритм с более низкой асимптотой c времени.
Наилучшее возможное время выполнения означает, что оно В самое лучшее время вы можете представить себе , что проблема может быть решена в, и это определенно невозможно для решения проблемы быстрее, чем это. Это быстрая проверка, которую вы делаете, чтобы исключить определенные подходы, которые не могли бы работать, потому что если бы они работали, они были бы слишком быстрыми.
Например проблема сортировки не может быть решена за среднее время O (n), потому что потребовалось бы время O (n) только для правильной записи / замены, чтобы расположить элементы на своих местах. Это не значит, что существует алгоритм, который сортирует по O (n) среднего времени, просто то, что определенно невозможно сделать лучше , чем O (n) в среднем.
Лучший аргумент может показать, что наилучшим возможным временем выполнения алгоритма сортировки на основе сравнения в среднем является O (n log n), поскольку каждое сравнение дает только один бит информации о том, в какой перестановке находится входной массив, поэтому нужно как минимум log 2 (n!) сравнений чтобы различать guish между всеми n! возможные перестановки. Поэтому невозможно написать алгоритм сортировки на основе сравнения, который использует один l oop над массивом и выполняет O (1) на одну итерацию; мы можем исключить эту возможность при попытке разработать алгоритм. В этом случае это алгоритмы сортировки на основе сравнения, которые удовлетворяют этой асимптотике c, поэтому она жесткая.
Так что, в некоторой степени, на самом деле не существует одного "лучшего мыслимого" время выполнения "для данной проблемы, это зависит от вашей способности доказать, что данное время выполнения является нижней границей всех возможных алгоритмов, решающих проблему.