Блог

У меня здесь есть 2 программы, которые отчаянно нуждаются в оценке эффективности с использованием нотации big o. Что касается первого, я не уверен в эффекте оператора if. У этого есть вложенный цикл, и они обычно имеют эффективность O (n ^ 2), но я не могу быть уверен. Другой также имеет вложенный цикл, но с командой break; .

 /* modifies a so that all the even numbers appear before
all of the odd numbers. there are multiple possible results
-the order of the even numbers does not matter
-the order of the odd numbers does not matter
*/

void even_first(int a[], int len) {
  int temp = 0;
  for (int i = 0; i < len;   i) {
    if (a[i] % 2 == 0) {
      temp = a[i];
      for (int j = i; j > 0; --j) {
        a[j] = a[j - 1];
      }
      a[0] = temp;
    }
  }
}
////////////////////////////////////////////////////////////////////
/*  finds the single integer in the inclusive range 1...[len   1] that does 
not appear in a. Because the elements of a are unique and all in the range
       1...(len   1), there must be a single integer in that range
that is "missing" from a */
int missing(int a[], int len) { 
  for (int j = 1; j <= len   1;   j) {
    bool found = false;
    for (int i = 0; i < len;   i) {
      if (a[i] == j) {
        found = true;
        break;
      }
    }
    if (!found) {
      return j;
    }
  }
  return -1;
}
 

Первый имеет временную сложность в наихудшем случае O (n ²) (все четные числа или, по крайней мере, количество четных чисел, масштабируемых по отношению к n, например, случайные целые числа). Эффект оператора if заключается в том, что он улучшает временную сложность в лучшем случае (все нечетные числа, поэтому оператор if всегда false и внутренний цикл никогда не выполняется), что равно O (n) . Сам внутренний цикл равен O (n), потому что число итераций все еще увеличивается на n .

Второй — O (n ²) в худшем случае, потому что он масштабируется с длиной массива и самим пропущенным числом. Если бы отсутствующий элемент всегда был равен 1, это было бы O (n), потому что внешний цикл выполнялся бы только один раз. Предполагая, что отсутствующий элемент является случайным, это O (n ²), потому что тогда оба цикла будут масштабироваться по длине.

Эффект оператора if в первой функции заключается в том, что второе n в n ^ 2 применяется только для четных чисел. Эффект более короткого цикла заключается в том, что он как бы делит второе n пополам. Если вы посмотрите на худший случай, все четы, вы получите n * (n 1) / 2, из-за этого более короткого цикла, который доходит до O (n ^ 2). Средний случай по-прежнему будет O (n ^ 2), хотя и с коэффициентом, близким к 1/4.

Редактировать: после прочтения некоторых комментариев я думаю, что мне следует добавить наилучшие, наихудшие и средние сценарии:

В лучшем случае нет четных, O (n)

В худшем случае все четные, O (n * (n 1) / 2) = O (n ^ 2)

Средний случай, половина четных O (n * (n 1) / 4) (средний результат для половины четных соответствует половине посещений в худшем случае) = O (n ^ 2)

Разрыв во второй функции сокращает второе n в n ^ 2 примерно до половины, так что, опять же, все еще O (n ^ 2).

Если вы пытаетесь добиться большего, чем O (n ^ 2), я почти уверен, что вы можете решить обе проблемы с помощью O (n), если просто создадите дополнительный массив, но вы только спросили, каков эффект оператора if и какова нотация big O.