Big O - Почему этот алгоритм O (AxB)?

Question

Я не уверен, почему этот код оценивается как O (A * B)?

void printUnorderedPairs(int[] arrayA, int[] arrayB) { 
  for (int i= 0; i < arrayA.length; i++) { 
    for (int j = 0; j < arrayB.length; j++) {
      for (int k=  0; k < 100000; k++) {
        System.out.println(arrayA[i] + "," + arrayB[j]); 
      }
    }
  }
}

Конечно, точнее, его O (1000 * A B), и мы опустили бы 1000, делая егоО (А В). Но что если массив A имеет длину 2? 1000 итераций не будут более значительными? Только потому, что мы знаем, что последний цикл является константой (и отображается его значение), мы не считаем его? Что если бы мы знали все размеры массивов?

Кто-нибудь может объяснить, почему мы не скажем его O (A B C)? Какой будет среда выполнения, если я сделаю код такой:

int[] arrayA = new int[20];
int[] arrayB = new int[500];
int[] arrayC = new int[100000];

void printUnorderedPairs(int[] arrayA, int[] arrayB) { 
  for (int i= 0; i < arrayA.length; i++) { 
    for (int j = 0; j < arrayB.length; j++) {
      for (int k=  0; k < arrayC.length; k++) {
        System.out.println(arrayA[i] + "," + arrayB[j]); 
      }
    }
  }
}

Answer 1

Если время выполнения (или количество шагов выполнения, или количество вызовов println, или то, что вы оцениваете с помощью своей записи Big O) равно O (AB), это означает, что время выполнения приближается к линейно пропорционально AB при росте AB без ограничения (приближается к бесконечности). Это буквально предел бесконечности, с точки зрения исчисления.

Большой О не имеет отношения к тому, что происходит для любого конечного числа итераций. Речь идет о предельном поведении функции, когда ее свободные переменные приближаются к бесконечности. Конечно, для небольших значений A вполне может существовать постоянный член, который доминирует во времени выполнения. Но когда A приближается к бесконечности, все эти другие факторы становятся незначительными.

Рассмотрим полином, подобный Ax^3 + Bx^2 + Cn + D. Он будет пропорционален x^3 при увеличении x до бесконечности - независимо от величины A, B, C или D. B может быть числом Грэм для всех забот Big O;бесконечность все еще намного больше, чем любое большое конечное число, которое вы выбираете, и поэтому доминирует член x ^ 3.

Итак, во-первых, учитывая , что если бы A было 2 , на самом деле не в духе AB приближается к бесконечности . Любое число, которое вы можете разместить на доске, в основном округляется до нуля. .

И, во-вторых, помните, что пропорционально AB означает равное AB умноженное на некоторую константу;и не имеет значения, что это за константа. Хорошо, если константа окажется равной 10000. Сказать, что что-то пропорционально 2N, то же самое, что сказать, что оно пропорционально N или любому другому числу, умноженному на N. Поэтому O (2N) такое же, как O (N). По соглашению мы всегда упрощаем использование нотации Big-O для отбрасывания любых постоянных факторов. Таким образом, мы всегда будем писать O (N), а не O (2N). И по этой же причине мы будем писать O (AB), а не O (10000AB).

И, наконец, мы не говорим O (ABC) только потому, что «C» (количество итераций вашего внутреннегоцикл в вашем вопросе) бывает константой;который также равен 10000. Вот почему мы говорим, что это O (AB), а не O (ABC), потому что C не является свободной переменной;он жестко запрограммирован на 10000. Если не предполагалось, что размер B не изменится (должен был быть постоянным по любой причине), то вы можете сказать, что это просто O (A). Но если вы позволите B расти без ограничений, то предел будет O (AB), а если вы также позволите C расти без границ, то предел будет O (ABC). Вы сами решаете, какие числа являются константами, а какие - свободными, в зависимости от контекста вашего анализа.

Подробнее о Big O нотации вы можете прочитать в Википедии.

Answer 2

Как правило, A*B не имеет значения, и это просто считается O(N).

Если бы было какое-то знание, что A и B были всегда в некоторой степенитакой же длины, то можно утверждать, что это действительно O(N^2).

Любая константа не имеет значения в нотации порядка, потому что для действительно очень больших чисел A / Bконстанта становится незначительной.

Answer 3

void printUnorderedPairs(int[] arrayA, int[] arrayB) { 
  for (int i= 0; i < arrayA.length; i++) { 
    for (int j = 0; j < arrayB.length; j++) {
      for (int k=  0; k < 100000; k++) {
        System.out.println(arrayA[i] + "," + arrayB[j]); 
      }
    }
  }
}

Этот код оценивается как O (A B), потому что arrayC имеет постоянную длину. Конечно, его время работы пропорционально A B * 100000. Здесь мы никогда не заботимся о постоянных значениях, потому что когда переменные становятся все выше и выше, например, 10 ^ 10000, константы могут быть легко проигнорированы.

Во втором коде мы говорим его O (1), потому что всемассивы имеют постоянную длину, и мы можем вычислить время их выполнения без какой-либо переменной.

Answer 4

Примите во внимание, что циклы for в i и j не зависят друг от друга, поэтому их время выполнения составляет O(A*B). Внутренний цикл в k представляет собой фиксированное число итераций, равное 100000, и также не зависит от двух внешних циклов, поэтому мы получаем O(100000*A*B). Но, поскольку цикл k является всего лишь постоянным (не переменным) штрафом, для общей сложности по-прежнему остается значение O(A*B).

Если вы записали внутренний цикл в k изОт 0 до C, тогда вы могли бы написать O(A*B*C) для сложности, и это также будет справедливо.