Временная сложность множества Мандельброта в терминах больших О

Question

Я пытаюсь найти временную сложность простой реализации множества Мандельброта. со следующим кодом

int main(){
    int rows, columns, iterations;
    rows = 22;
    columns = 72;
    iterations = 28;

    char matrix[max_rows][max_columns];

    for(int r = 0; r < rows; ++r){
        for(int c = 0; c < columns; ++c){
            complex<float> z;
            int itr = 0;
            while(abs(z) < 2 && ++itr < iterations)
                z = pow(z, 2) + decltype(z)((float)c * 2 / columns - 1.5,
                    (float)r * 2 / rows - 1);
            matrix[r][c]=(itr== iterations ? '*' : '.');
        }
    }

Теперь, взглянув на приведенный выше код, я сделал некоторую оценку сложности времени в терминах большой O-нотации и хочу узнать, верна она или нет

Таким образом, мы создаем двумерный массив, проходящий через вложенные циклы, и на каждом элементе мы выполняем операцию и устанавливаем значение этого элемента, если мы принимаем n в качестве входного размера, мы можем сказать, что чем больше входное значение, тем больше будет будет сложность, поэтому временная сложность для строк xcolumns будет O (rxc), и затем мы снова пройдем ее для распечатки, так, какова будет временная сложность? это O (RXC) + O (RXC)? влияет ли сама функция на сложность времени, когда мы выполняем умножение и вычитание строк и столбцов? Если да, то как?

Answer 1

Почти, учитывая r строк, c столбцов и i итераций, тогда время выполнения составляет O(r*c*i).Это должно быть тривиально, чтобы увидеть, если abs(z)<2 там нет.Но с этим дополнительным условием неясно, сколько раз в общей сложности будет работать внутренний цикл while.Да, это будет меньше, чем r*c*i раз, поэтому O(r*c*i) по-прежнему является верхней границей.Но, возможно, мы могли бы сделать лучше.Учитывая, что для любого r,c вы вычисляете множество Мандельброта в одном и том же домене с переменным разрешением, тогда цикл while будет выполняться k*r*c*i раз для некоторой константы k, которая находится где-то между областью Мандельброта-набор-над-областью-of-of-domain и 1 -> Время выполнения кода Θ(r*c*i), и O(r*c*i) не может быть улучшено.

Если бы вы вычислили установленный для [-c,c]x[-r,r] домен с фиксированным разрешением, то для любого |z|>2 abs(z)<2 прерывается после первой итерации.Тогда O(r*c*i) не будет жестко ограниченным, и это условие (как и все условия цикла) следует учитывать, если вы хотите получить точную оценку.

Пожалуйста, не используйте malloc, std::vector безопаснее.

Answer 2

В обозначении big-O O (rxc) + O (rxc) падает до O (rxc).

Поскольку максимальный счетчик итераций также является входной переменной, он также влияет на сложность. В частности, внутренний цикл выполняется не более чем n итераций, поэтому ваша сложность равна O (rxcxn).

Все остальные операции являются постоянными, в частности умножение и сложение complex<float>. Эти операции сами по себе всегда являются O (1), что не влияет на общую сложность.