Для измерения сложности алгоритма это сложность времени или вычислительная сложность? В чем разница между ними?
Я использовал для расчета максимального (наихудшего) количества основных (наиболее затратных) операций в алгоритме.
complexity-theory
terminology
algorithm-analysis
time-complexity
Медиана Хилал
источник
источник
Ответы:
Вычислительная сложность - это просто более общий термин, поскольку время - не единственный ресурс, который мы могли бы рассмотреть. Следующим наиболее очевидным является пространство, которое использует алгоритм, и, следовательно, мы можем говорить о сложности пространства , также как о части вычислительной сложности. Действительно, мы можем сделать это для любой меры, которую вы используете, конечно, некоторые меры более полезны, чем другие.
Таким образом, подсчет количества шагов, которые алгоритм выполняет в наихудшем случае, дает оценку сложности времени для решаемой проблемы, подсчет того, сколько памяти / сколько ленточных элементов он использует, дает оценку сложности пространства и т. Д. И т. Д.
Помните также, что если вы хотите быть строгим, сложность относится к проблеме, а не к алгоритму, поэтому у проблемы есть границы сложности, у алгоритма есть границы ресурсов (время выполнения, использование пространства ...). Это просто вопрос формальности определения, теория сложности решает проблемы. Да, алгоритмы являются ключевым инструментом для анализа проблем и сложности, а алгоритмы тесно связаны друг с другом, но формально мы бы не сказали, что Merge-Sort (алгоритм) находится в , это проблема S o r t i n g, которая находится в P . Merge-Sort использует определенные ресурсы ( O ( n log n )P Sorting п O ( n logн ) шаги например). Оценка ресурса и правильность алгоритма подразумевают сложность (верхнюю) оценку проблемы, но это разные вещи. также Т С 0 -полным под С 0 -reductions, эта сложность связана только действительно может быть указано для задачи (но имеет алгоритмические последствия).S o r t i n g TС0 A C0
источник
Цикломатическая сложность часто используется в качестве меры вычислительной сложности. Полезный пример приведен в /programming/9097987/calculation-of-cyclomatic-complexity.
В алгоритме может быть много разных (возможно, вложенных) путей, что придает ему высокую цикломатическую сложность, но не может быть циклов, дающих ему низкую временную сложность. Программа с одним циклом будет иметь низкую цикломатическую сложность, но, возможно, высокую временную сложность.
Цикломатическая сложность часто используется как мера обслуживания, необходимого для кода. Более подробное обсуждение приведено в http://docs.sonarqube.org/display/SONAR/Bad+Distribution+of+Complexity . Это отличается от сложности времени, которая является измерением времени выполнения кода и может использоваться для оценки восприятия пользователями эффективности системы.
источник