Продолжить инстр. и сложность времени в цикле for в переполнении стека
Я размышлял ….
Как функция «continue» в цикле for в C ++ влияет на временную сложность функции, например:
for( int i(0); i < size; i++)
{
if( array [i] == i ) continue;
while( j < array[i]/3 )
{
array2[j] = array [i];
j += 2;
}
}
Решение
Не обращая внимания на все константы, вы должны учитывать наихудший случай, если вы ищете большой О.
continue в этом примере не влияет на большой O, потому что вы должны учитывать возможность того, что предыдущий if условие никогда не выполняется. Таким образом, у вас есть O(n*m)
Лучший результат будет O(n) в том случае, если внутренний цикл никогда поступил. if ... continue также не имеет никакого влияния на это значение (хотя это может привести к тому, что оно будет происходить чаще). Без if ... continue у вас еще есть дело, что j < array[i]/3 никогда не бывает правдой Таким образом, внутренний цикл никогда не вводится, что оставляет тело внешнего цикла как O(1) дающий O(n) с или без continue
Другие решения
Если вы предполагаете сложность времени как большую О, вас интересует наихудший случай, тогда вы должны предположить, что «продолжить» никогда не сработает.
detector