Sergey Alexandrovich Kryukov
Это не всегда возможно, это возможно только в особых случаях. Сложность не "вычисляется", она доказывается, как математические теоремы.
—СА
Это не всегда возможно, это возможно только в особых случаях. Сложность не "вычисляется", она доказывается, как математические теоремы.
—СА
Пожалуйста, смотрите мой комментарий к этому вопросу. Временная сложность не вычисляется, не в арифметическом смысле этого слова. Надеюсь, вы понимаете, что сложность времени не измеряется в секундах. Пожалуйста смотрите:
http://en.wikipedia.org/wiki/Time_complexity[^],
http://en.wikipedia.org/wiki/Big_O_notation[^].
Например, для (int index = 0; index < length; ++index) { doSomething(index); } ответ-O(n). Откуда мы это знаем? Потому что, по - видимому, количество звонков в doSomething и, следовательно, время - это линейная функция времени. length Когда мы сможем вычислить и классифицировать такую функцию, мы сможем выяснить, что такое класс сложности.
Также очевидно, что это не всегда возможно. В конце концов, доказано, что можно создать алгоритм с непредсказуемым поведением, поэтому поиск временной сложности может быть теоретически неразрешимой проблемой, или понятие временной сложности может быть вообще неприменимо.
Мне понравилась информация, представленная здесь (http://discrete.gr/complexity/) очень много, когда я впервые прочитал его.
Похоже, это интересный ресурс. Вы можете добавить его как отдельный формальный ответ...
—СА
Я думал, что помещу его в качестве комментария (своего рода дополнения) к вашему сообщению :). Добавит ли это какую-то ценность, если это будет пост как отдельное решение?
Да, немного. Если какой-либо пост имеет некоторую ценность как хороший совет или ресурс и имеет отношение к теме вопроса или даже к какому-то последующему вопросу, всегда имеет смысл опубликовать его как решение. Помимо всего прочего, это даст возможность другим членам проголосовать за него. :-)
Мы часто делимся некоторыми интересными мыслями, которые могут послужить или не послужить полезным советом. Когда мы не совсем уверены, что это правильно, комментарий-лучшая форма для поста...
—СА
+5
Спасибо.
—СА