#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) .
- Создайте набор.
- Для каждого из
m
элементовsource
,- Давайте назовем
s
значение текущего элемента. - Если набор не содержит
s
,- Добавьте
s
в набор.
- Добавьте
- Давайте назовем
- Для каждого элемента
n*n
элементовtarget
,- Давайте назовем
v
значение текущего элемента. - Если набор содержит
s
,- Добавьте единицу к
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) из ваших трех петель внутри друг друга.