Сложность времени операторов if-else в цикле for

Question

Пусть A [1, ..., n] - это массив, хранящий бит (1 или 0) в каждом месте, а f (m) - это функция, временная сложность которой θ (м). Рассмотрим следующий фрагмент программы, написанной на C, как язык:

Случай 1: -

counter = 0; 
for (i = 1; i < = n; i++) 
{ 
    if (A[i] == 1) 
    counter++; 
    else { 
    f(counter); 
    counter = 0; 
    } 
} 

Случай 2: -

counter = 0; 
for (i = 1; i < = n; i++) 
{ 
    if (A[i] == 1) 
    counter++; 
    else { 
    counter = 0; 
    f(counter); 
    } 
} 

Сложность этого фрагмента программы является

(A) Ω (n2)

(B) Ω (nlog n) и O (n2)

(C) θ (п)

(D) O (п)

вопрос как я знаю, что, когда, если заявление или иное выражение используется и когда функция е (т) Как я подхожу к нему? я могу рассматривать случаи, когда только если выполняется или только иначе, но что касается общего случая, когда оператор if выполняется иногда и в другом случае иногда

Answer 1

Мы можем начать с рассмотрения простого случая, случая 2. Ясно, каждый раз, когда мы пройти через петлю в случае 2, один из либо 2 вещей происходит:

1. счетчика увеличивается (который занимает O (1) [за исключением not really, но мы просто сказать, что это делает для компьютеров, работающих на номера фиксированной длины (т. е. 32-битные ints)])
2. count установлен в 0 (что принимает O (1) [снова, дискуссивно]) и вычисляется f (count) (что определенно занимает постоянное время)

мы проходим через петлю n раз, каждый раз занимает практически время O (1), bada-bing, bada-boom, требуется O (n) (или O (n * lg (n)), если вы педантичны и используете целые числа переменной длины).

Дело 1, с другой стороны, требует немного математического мышления.

Битовые строки, которые занимают кратчайший промежуток времени в случае 1, являются, очевидно, 11111....11111, 000....000, 000...0111...111 или аналогичными. Все они занимают время θ (n) для завершения, устанавливая нижнюю границу для случая 1. Теперь нам нужно установить наихудший сценарий.

Не вдаваясь в строгости надлежащего доказательства, это довольно просто утверждать, что битовые строки наихудшие выглядеть следующим образом:

111....1110 

Немного нитка выше формы с длиной 100 будет иметь 99 1, и для этого потребуется 99 + 99 единиц времени. Строка длины n явно требует 2(n - 1) единиц времени.

Это, очевидно, все еще линейно по n, поэтому случай 1, даже в худшем случае, равен θ (n).

Потому что оба случая 1 и случай 2 являются θ (n), проблема θ (n).

---

Если вам все еще нужно, чтобы убедиться в том, что 11.....110 наихудшей битовой строке, подумайте:

A bit string of the form 
|--------------n bits------------| 
1....101....101....10......1....10 
|-L1-| |-L2-| |-L3-|  |-Lm-| 
11110 
Where L1 - Lm are arbitrary integers will require time 
t = (L1) + (L2) + (L3) + ... + (Lm) + (n - m) 
    = sum(L1 to Lm) - m + n 

the more "runs" of ones there are, the larger the - m factor is. If we 
just have one big "run" of ones, we have 

t = n - 1 + n - 1 = 2(n - 1) 

---

Как matter of principle, я не отвечаю плохо задаваемые вопросы домашнего задания на переполнение стека.

После разговора с coder101 в чате, однако, он/она показала мне, что это НЕ проблемы домашних заданий, но вместо того, чтобы проблема, которая была извлечена из онлайновой базы данных here, которая призвана обеспечить «фиктивные тесты для вундеркиндов ". Это похоже на вызов, который кодер101 наделил собой, и хотя это может быть лучший вопрос, я не думаю, что это так плохо.