Рассчитать время / пространство сложности при запуске программы

Question

Я пробую различные типы алгоритмов сортировки и понимаю концепцию асимптотической сложности времени и пространства.

Мне интересно, можем ли мы написать какую-то логику в самой программе, чтобы вычислить пространственно-временную сложность этого алгоритма, чтобы у нас было доказательство того, что алгоритм ведет себя так, как ожидалось?

У кого-нибудь есть мысли по этому поводу?

Answer 1

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

Вам нужно будет перечислить все возможные экземпляры, потому что вы не знаете, какие входные данные будут сложными, а какие - нетрудными. Например, если бы вы тестировали BubbleSort с упорядоченными входами от 1... n с переменной длиной, вы бы никогда не наблюдали худший случай.