Я не совсем уверен, равен ли Большой O моего алгоритма O (n ^ 3) или O (m * n * n)

#c #big-o #nested-loops

#c #big-o #вложенные циклы

Вопрос:

Итак, я пытаюсь найти Большой O моего алгоритма ниже.

 for(int x=0;x<m;x  ){
    for(int y=0;y<n;y  ){
        for(int z=0;z<n;z  ){
            if(target[x][y]==source[z]) count  ;
        }
    }
}
  

Но я не совсем уверен, является ли это O (n ^ 3) или O (m * n * n) …

Ответ №1:

Каждый цикл не зависит от других, за исключением того, что он вложен, так что это простое умножение количества проходов, которые каждый выполняет: O (m * n * n) = O (m * n 2).

Это означает, что производительность будет линейно увеличиваться по мере m увеличения и квадратично по мере n увеличения. Если оба увеличатся, производительность будет увеличиваться на их произведение.

Если между и нет какой-либо неустановленной связи m n , это нельзя обобщить на O (n 3) . Напротив, если нет никакой связи, вы могли бы даже рассмотреть алгоритм O (m) (если вас не интересует, что происходит при n масштабировании) или O (n 2) (если вас не интересует, что происходит при m масштабировании).


Обратите внимание, что такой поиск может быть выполнен в O (m n 2) .

  1. Создайте набор.
  2. Для каждого из m элементов source ,
    1. Давайте назовем s значение текущего элемента.
    2. Если набор не содержит s ,
      1. Добавьте s в набор.
  3. Для каждого элемента n*n элементов target ,
    1. Давайте назовем v значение текущего элемента.
    2. Если набор содержит s ,
      1. Добавьте единицу к count .

Это предполагает, что поиск по набору равен O (1), а добавление к набору равно O (1) (амортизировано).

Ответ №2:

Мне кажется, что это O (m * n * n), что равно O (m * n 2), поскольку ваш внешний цикл повторяется m , но каждый из ваших двух внутренних циклов повторяется n .

Ответ №3:

цикл O(n). цикл внутри цикла O (n * n) или O (n ^ 2). цикл внутри цикла внутри другого цикла O (n * n * n) или O (n ^ 3).

Зависит ли ваш самый внешний цикл от n или m? Конечно, вы не можете просто пренебречь внешним циклом, поскольку его не было.

Поэтому O (m * n * n) из ваших трех петель внутри друг друга.