Я пытаюсь использовать различные типы алгоритмов сортировки, и я понимаю понятие асимптотической сложности времени и пространства.вычислить сложность времени/пространства во время работы программы
Мне интересно, можем ли мы написать какую-либо логику в самой программе, чтобы вычислить сложность пространства/времени этого алгоритма, чтобы мы могли иметь доказательство того, что алгоритм ведет себя так, как ожидалось?
У кого-нибудь есть мысли по этому поводу?
С помощью инструментария вы можете измерить время и пространство, используемые для конкретного экземпляра проблемы. Только если вы перечислили все возможные проблемы, вы сможете доказать худшую временную и пространственную сложность. На практике это довольно неоспоримо.
Вам нужно будет перечислить все возможные экземпляры, потому что вы не знаете, какие входы будут сложными и что будет легко. Например, если вы должны были тестировать BubbleSort с упорядоченными вводами 1 ... n с переменной длиной, вы никогда не заметите худший случай.
Я не понял вас полностью. Не могли бы вы получить дополнительную информацию или ссылку, чтобы уточнить ваш ответ. – Onki
Не проблема. Но не могли бы вы сказать мне, какой бит неясен. – mpkorstanje
У вас может быть время вашего алгоритма с множеством входных длин, а затем определить, как шкала времени основана на входных длинах (например: линейная шкала времени линейно с увеличением входа). – Buddy
_Proving_, что алгоритм имеет указанное худшее поведение, не представляется возможным. –