Big O нотация для сравнения строк algo

Question

Какими будут большие обозначения O функции foo?

int foo(char *s1, char *s2)
{
   int c=0, s, p, found;
   for (s=0; s1[s] != '\0'; s++)
   {
      for (p=0, found=0; s2[p] != '\0'; p++)
      {
         if (s2[p] == s1[s])
         {
            found = 1;
            break;
         }
      }
      if (!found) c++;
   }
   return c;
}

Какова эффективность функции foo?

a) O (n!)

b) O (n ^ 2)

c) O (n lg (base2) n)

d) O (n)

Я бы сказал O(MN) ...

Answer 1

Это O(n²), где n = max (длина (s1), длина (s2)) (которая может быть определена менее чем за квадратичное время - см. Ниже).Давайте посмотрим на определение в учебнике:

f (n) ∈ O (g (n)), если существует положительное действительное число c и положительное целое число N, такие что f (n) <= cg(n) для всех n> = N

По этому определению мы видим, что n представляет число - в этом случае это число является длиной передаваемой строки. Однако существует очевидное расхождение, поскольку это определение предусматривает только одну переменную функцию f(n), и здесь мы явно передаем 2 строки с независимыми длинами.Поэтому мы ищем многопараметрическое определение для Big O. Однако, как продемонстрировал Хауэлл в «Об асимптотической записи с несколькими переменными» :

«невозможно определить big-O нотация для многопеременных функций таким образом, что подразумевает все эти [обычно предполагаемые] свойства. "

На самом деле существует формальное определение для Big O с несколькими переменными однако это требует дополнительных ограничений, выходящих за пределы единственной переменной Big O, и выходит за рамки большинства (если не всех) курсов алгоритмов.Для анализа типичного алгоритма мы можем эффективно свести нашу функцию к одной переменной, привязав все переменные к ограничивающей переменной n.В этом случае переменные (в частности, длина (s1) и длина (s2)) явно независимы, но их можно связать:

Метод 1

Let x1 = length(s1)
Let x2 = length(s2)

Наихудший сценарий для этой функции возникает при отсутствии совпадений, поэтому мы выполняем итерации x1 * x2.

Поскольку умножение является коммутативным, наихудший сценарий foo (s1, s2) == наихудшийсценарий foo (s2, s1).Поэтому мы можем предположить без ограничения общности, что x1> = x2.(Это потому, что если x1

Метод 2 (если вам не нравится первый метод)

Для сценария наихудшего случая (в котором s1 и s2 не содержат общих символов), мы можем определить длину (s1) и длину (s2) до итерации циклов (в .NET и Java, определяядлина строки составляет O (1), но в этом случае это O (n)), назначая большее x1 и меньшее x2.Здесь ясно, что x1> = x2.

Для этого сценария мы увидим, что дополнительные вычисления для определения x1 и x2 делают это O (n² + 2n). Мы используем следующее правило упрощения , котороеможно найти здесь для упрощения до O (n²):

Если f (x) является суммой нескольких слагаемых, один с наибольшим темпом роста сохраняется, а все остальные опускаются.

Заключение

для n = x1 (наша ограничивающая переменная), так что x1 >= x2, наихудший сценарий - x1 = x2.Поэтому: f(x1) ∈ O(n²)

Дополнительная подсказка

Для всех домашних заданий, связанных с SO, связанных с обозначением Big O , если ответ не одиниз:

O(1)
O(log log n)
O(log n)
O(n^c), 0<c<1
O(n)
O(n log n) = O(log n!)
O(n^2)
O(n^c)
O(c^n)
O(n!)

Тогда вопрос в , вероятно, , лучше быть отправленным на https://math.stackexchange.com/

Answer 2

В нотации big-O мы всегда должны определять, что означают переменные. O(n) ничего не значит, если мы не определим, что такое n. Часто мы можем опустить эту информацию, потому что это ясно из контекста. Например, если мы говорим, что какой-то алгоритм сортировки имеет вид O(n log(n)), n всегда обозначает количество элементов для сортировки, поэтому нам не нужно всегда указывать это.

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

В приведенном вами примере вы взяли m и n в качестве соответствующих длин двух строк. При таком определении алгоритм действительно O(m n). Если мы определим n как длину более длинной из двух строк, мы также можем записать это как O(n^2) - это также верхний предел сложности алгоритма. И с таким же определением n алгоритм также O(n!), но не O(n) или O(n log(n)).

Answer 3

Думайте об этом так:

Есть два входа.Если функция просто возвращается, то ее производительность не связана с аргументами.Это будет O (1).

Если функция зациклена на одной строке, то производительность линейно связана с длиной этой строки.Следовательно, O (N).

Но у функции есть цикл внутри цикла.Производительность связана с длиной s1 и длиной S2.Умножьте эти длины вместе, и вы получите количество итераций цикла.Это уже не линейно, оно следует кривой.Это O (N ^ 2).

Answer 4

O (n ^ 2)

Соответствующей частью функции, с точки зрения сложности, являются вложенные циклы.Максимальное количество итераций - это длина s1, умноженная на длину s2, причем оба являются линейными коэффициентами, поэтому время вычисления в худшем случае составляет O (n ^ 2), т. Е. Квадрат линейного коэффициента.Как сказал Итан, O (mn) и O (n ^ 2) фактически одно и то же.