Временная сложность функции с циклами while и оператором if

Question

int dup_chk(int a[], int length) 
{
  int i = length;
  while (i > 0)
  {
    i--;
    int j = i -1;
    while (j >= 0)
    {
      if (a[i] == a[j])
      {
        return 1;
      }
      j--;
    }
  }
  return 0;
}

Итак, я знаю следующее:

• строка 1 равна всего лишь 1.
• Первый цикл равен N + 1.
• я--;N раз, начиная с первого цикла while.
• j = i -1;также равно N.
• Второй цикл while (N + 1) N = N ^ 2 + N, поскольку цикл while внутри цикла while
• if:
• j--;является N (N) = N ^ 2
• return 0;это 1

Я действительно новичок в расчете временной сложности алгоритмов, поэтому я даже не уверен, что то, что я знаю, абсолютно верно.Но что мне мешает, так это утверждение if, я не знаю, как его вычислить (и что, если после него есть еще else?)

РЕДАКТИРОВАТЬ: общая сумма равна 3 / 2N^ 2 + 5 / 2N + 3 Я понимаю, что эта функция есть O (N ^ 2), но не совсем понимаю, как рассчитывался общий итог.

Answer 1

Тщательная оценка:

Эта программа имеет специальную функцию: она завершается, если найдена пара (a[I], a[J]) равных значений.Предположим, что мы знаем I и J (позже мы увидим, что если такой пары нет).

Внешний цикл выполняется для всех I <= i < L, следовательно, L-I раз.Каждый раз внутренний цикл выполняется для всех 0 <= j < i, следовательно, i раз, кроме последнего прохода (i = I): у нас есть J <= j < I, следовательно, I-J итераций.

Мы предполагаемчто «стоимость» цикла имеет вид a N + b, где a - это стоимость одной итерации и b некоторые постоянные издержки.

Теперь для внутреннего цикла, который выполняетсяL-I раза с уменьшением количества итераций, используя формулу "треугольных чисел", стоимость составляет

a (L-1 + L-2 + ... I+1 + I-J) + b (L - I) = a ((L-1)L/2 - I(I+1)/2 + I-J) + b (L-I)

, к которой мы добавляем стоимость внешнего цикла, чтобы получить

a ((L-1)L/2 - I(I+1)/2 + I-J) + b (L-I) + c

(где b - это константа, отличная от приведенной выше).

Обычно эта функция квадратична в L, но если пара быстро обнаруживается (скажем, I = L-3), она становится линейной;в лучшем случае (I = L-1, J = L-2) это даже постоянная a + b + c.

Наихудший случай происходит, когда пара находится последней (I = 1, J = 0), чтопрактически эквивалентно не найдена пара.Тогда у нас есть

a (L-1)L/2 + b (L - 1) + c

очевидно O(L²).

Answer 2

Обычно такой точный анализ сложности времени не требуется.Достаточно знать это с точки зрения Big-O.Тем не менее, я сделал некоторые расчеты для своего собственного любопытства.

Если ваша задача - просто анализ наихудшего случая для определения сложности времени, рассмотрим массив, содержащий только уникальные элементы.В таком случае:

• Оператор return 1 никогда не выполняется.Внутренний цикл while выполняется N (N-1) / 2 раза (суммирование i-1 от 1 до N), и происходят три вещи: проверяется условие while (и оценивается как true), условие ifпроверяется (и оценивается как ложное), а переменная j уменьшается.Таким образом, число операций равно 3N (N-1) /2.
• Внешний цикл while выполняется N раз, и кроме проверки состояния есть три оператора - i уменьшается на единицу, j назначается, и внутреннее условие while не выполняется N раз.Это на 4N больше операций.
• Вне всех циклов есть еще три оператора.Инициализация i, условие while не выполняется один раз, а затем оператор return.Добавьте еще 3 к нашему счету.

3 / 2N ² - 3 / 2N + 4N + 3.

Это 3 / 2N ² + 5 / 2N + 3. Вот ваш «общий итог».

Повторюсь, этот расчет совершенно не нужен для всех практических целей.

Answer 3

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

int dup_chk(int a[], int length)
{
    int j = 0;
    int i = length;
    char stringa[30];

    printf("Before first while loop j = %d and i = %d \n", j, i);
    while (i > 0)
    {
        i--;
    j = i - 1;
    printf("\tIn first while loop j = %d and i = %d\n", j, i);
    while (j >= 0)
    {
        printf("\t\tIn second while loop j = %d and i = %d\n", j, i);
        if (a[i] == a[j])
        {
            printf("\t\tIn if statment j = %d and i = %d\n", j, i);
            return 1;
        }
        j--;
        printf("\t\tEnd of second while loop j = %d and i = %d\n", j, i);
    }
}
printf("After first while loop j = %d and i = %d \n", j, i);
printf("Press any key to finish the program and close the window\n");
return 0;
}

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

Answer 4

int dup_chk(int a[], int length) 
{
  int i = length;
  while (i > 0)  // Outer loop
  {
    i--;
    int j = i -1;
    while (j >= 0)  // Inner loop
    {
      if (a[i] == a[j])
      {
        return 1;
      }
      j--;
    }
  }
  return 0;
}

Вышеприведенная программа является именно вашим кодом с двумя комментариями, которые я позволил себе добавить.

Давайте рассмотрим наихудший сценарий (потому что это то, что всех волнует / беспокоит).Если вы внимательно заметите, вы заметите, что для каждого значения i, Inner loop выполняется i - 1 раз.Таким образом, если ваше Outer loop выполнено n раз, Inner loop будет выполнено в общей сложности n * (n - 1) раз (т.е. n - 1 раз для каждого значения n).

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

В этом прелесть и простота записи Big-O.- Цитируя Джонатана Леффлера из комментариев выше.

Answer 5

Проверка if выполняется столько раз, сколько повторяется внутренний цикл while.

return 1 по определению выполняется только один раз, макс.Похоже, вы предполагаете, что на входе нет дубликатов (т. Е. В худшем случае), и в этом случае оператор return 1 никогда не выполняется.

В конечном итоге вы почувствуете, какие части кода вы можете использовать.игнорировать, так что вам не нужно будет вычислять этот «общий итог», а просто понять, что есть два вложенных цикла, каждый из которых пересекает массив - т.е.O (N ^ 2).