Насколько отличается временная сложность между этими двумя кодами?
Я сейчас изучаю алгоритмы, и разница во времени между этими двумя кодами более чем в 100 раз.
input
- Длина строки находится в диапазоне
1<= Length <= 1000000
Эти два кода являются частью кода, используемого для решения задачи алгоритма.
string cutstring(string str, int i, int j) {
string cup = "";
for (int p = i; p <= j; p++) {
cup += str[p];
}
return cup;
}
bool strComp(string str,int i,int j) {
if (cutstring(str, i, j) == "IOI")
return 1;
else
return 0;
}
Этот код быстрее, чем первый код.
bool strComp(string str,int i,int j) {
if (str[i] == 'I' && str[i+1]=='O' && str[i+2] == 'I')
return 1;
else
return 0;
}
Мне интересно, почему такая значительная разница во времени между этими двумя кодами Любое объяснение будет полезно и высоко оценено.
Всегда ли ji+2? Потому что иначе эти функции не делают одно и то же. Также i лучше быть меньше, чем str.size()-2.
j всегда i+2
Потому что первая реализация использует безумно дорогие операции, такие как '+=', без видимой причины (и, вероятно, скомпилирована без оптимизаций, что гарантирует, что безумно дорогие операции никуда не денутся и останутся безумно дорогими).
Если j всегда i+2, в чем причина его существования?
В 1000 раз больше времени равно O(x). Даже в 10000000000 раз медленнее будет тот же O (x)
Не используйте 1 и 0 для логических значений, используйте true и false. И if (boolean_expression) return true; else return false; --> return boolean_expression;
Ответы 1
Есть вещи, которые происходят в первом примере кода, но не происходят во втором, в частности:
- строка
strкопируется в аргументcutstring, поскольку она передается по значению (и, следовательно, должна быть скопирована). Для больших строк (длиной до 1000000) это может занять очень много времени, так как необходимо выделить новую память и скопировать всю строку. - строка
cupвcutstringсоздается и расширяется несколько раз. На платформах, которые не используют оптимизацию небольших строк, это может привести к нескольким перераспределениям памяти.
Я думаю, что первый пункт является наиболее впечатляющим. Вы можете попробовать передать строку по ссылке (string const& str вместо string str) и посмотреть, изменит ли это время.
Второй момент трудно диагностировать удаленно, потому что вы не предоставили никакой информации о том, как вы компилируете свой код (какой компилятор и какие флаги компиляции) и как вы измеряете время. Как правило, эта информация жизненно важна для вопросов, связанных с производительностью / эталонными показателями.
И последнее замечание, если позволите: временная сложность не имеет ко всему этому никакого отношения. Как было указано в комментариях к вашему вопросу, постоянный фактор между временем выполнения означает, что два алгоритма имеют одинаковую сложность. Это прекрасный пример того, почему сложность времени выполнения представляет больше теоретический интерес, потому что для оценки фактической производительности вашего кода вы всегда должны измерять.
Ну, вызов функции имеет некоторое влияние на производительность? Также проверьте, включены ли все флаги оптимизации.