Обозначение Big-O для алгоритма клеточного автомата - PullRequest
Новая
       41

Обозначение Big-O для алгоритма клеточного автомата

1 голос
/ 19 марта 2019

Задача

Я новичок в Big-O нотации, пытаюсь найти нотацию Big-O для алгоритма клеточного автомата.

Алгоритм

Я использую следующий алгоритм: 

Ai-1 = Ai;
Row_Rand = Random(1,ny);
Col_Rand = Random(1,nx);
For r = 1:ny
    For c = 1:nx
        IF Col_Rand(c) == 1
            Ai (Row_Rand(r),Col_Rand(c))= Boundary_Rules(bi2dec(Ai-1(Row_Rand(r),Col_Rand(c)), Ai-1(Row_Rand(r),Col_Rand(c)),, Ai-1(Row_Rand(r),Col_Rand(c)+1)));
        ELSEIF Col_Rand(c) == nx
            Ai (Row_Rand(r),Col_Rand(c))= Boundary_Rules(bi2dec(Ai-1(Row_Rand(r),Col_Rand(c)-1), Ai-1(Row_Rand(r),Col_Rand(c)),, Ai-1(Row_Rand(r),Col_Rand(c))));
        ELSE
            Ai (Row_Rand(r),Col_Rand(c))= Rules(bi2dec(Ai-1(Row_Rand(r),Col_Rand(c)-1), Ai-1(Row_Rand(r),Col_Rand(c)), Ai-1(Row_Rand(r),Col_Rand(c)+1)));
        END
    END
END

Предполагая, что:

  • Матрицы "Ai", "Boundary_Rules" и "Rules" уже определены в памяти.
  • Переменные «ny» и «nx» уже определены в памяти и соответствуют количеству пикселей на изображении в обоих направлениях y и x соответственно.
  • Функция «Случайно» - это современная функция «Перестановка Фишера-Йейтса» с O (N) , где N - размер пространства для перемешивания.
  • Функция "bi2dec" превращает двоичные значения, хранящиеся в Ai-1, в десятичное значение для обращения к массиву.

Правильно ли было бы сказать, что для этого алгоритма запись Big-O равна O (ny * nx) = O (N) (где N = ny * nx, общее количество пикселей в изображении).

Кроме того, если бы этот алгоритм затем был вложен в цикл for, который выполняется для обозначенного числа итераций ( Nit ), то запись Big-O стала бы O (Nit * N) , где Nit станет доминирующим фактором, если он больше, чем N?

...