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