Какова временная сложность этого фрагмента кода?

void push(const Type& e){ 
     if (size() == CAP) { 
      CAP = CAP + 100; 
      Type * Snew = new Type[CAP]; 
      for (int i = 0; i < CAP - 100; i++){ 
       Snew[i] = S[i]; 
      } 
      delete[] S; 
      S = Snew; 
     } 
     TOP++; 
     S[TOP] = e; 
    }

Какова временная сложность этого алгоритма и почему? Я смотрю на это, надеясь, что я не ошибаюсь, но я думаю, что он имеет сложность линейного времени (O (n)) из-за наличия одного цикла для цикла, и я думаю, что любая другая операция за пределами цикла является постоянное время работы.Какова временная сложность этого фрагмента кода?

источник

2015-02-01 user11892

Вы правы, за исключением того факта, что у вас нет никакого 'n' в вашем коде. Сложность времени - «O (CAP)». –

Оба размера() и назначение внутри цикла могут иметь любую сложность, что делает вопрос неопровержимым без дополнительной информации. Кроме того, вы, вероятно, хотите рассмотреть амортизированную стоимость: средняя стоимость вызова функции, если вы называете ее n раз. Таким образом, вы увидите разницу между CAP + 100 (средняя стоимость O (n)) и CAP * 2 (средняя стоимость O (1)), если недостающим кодом является все O (1). –

Это O (n), все в порядке. В зависимости от реализации new это может также быть O (n) вместо константы (если это очистка mem или что-то еще), но это все еще делает всю вещь O (n).

источник

2015-02-01 06:45:12

Сложность - O (n). Однако обратите внимание, что большинство реализаций стека удваивают размер массива, а не увеличивают его на фиксированную сумму, чтобы достичь амортизированного постоянного времени. См. Constant Amortized Time для обсуждения.

источник

2015-02-01 10:35:17 markusk

Какова временная сложность этого фрагмента кода?

ответ

Смежные вопросы