Объясните временную сложность?

То, что вы ищете в большой временной сложности O, - это приблизительное количество раз, когда инструкция выполняется. Итак, в первой функции у вас есть исполняемый оператор:

intMatrix[i][j] = 0;

Поскольку исполняемый оператор каждый раз занимает одинаковое количество времени, он равен O (1). Итак, для первой функции вы можете сократить ее, чтобы она выглядела так, и вернуться к исполняемому оператору:

i: execute n times{//Time complexity=n*(n+1)/2
    j: execute i times{
        intMatrix[i][j] = 0; //Time complexity=1
    }
}

Возвращаясь назад, цикл i выполняется n раз, а цикл j выполняется i раз. Например, если n = 5, количество выполняемых инструкций будет 5+4+3+2+1=15. Это арифметический ряд, и его можно представить как n(n+1)/2. Таким образом, временная сложность функции составляет n(n+1)/2=n^2/2+n/2=O(n^2).

Для второй функции вы смотрите на что-то подобное. Ваш исполняемый оператор:

dividend[j] = dividend[j] / divisor[i];

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

i: execute n times{ //Time complexity=n*(n*(1*m^2))=O(n^2*m^2)
    j: execute n times{ //Time complexity=n*(1*m^2)
        if statement: execute ONCE{ //Time complexity=1*m^2
            dividend[j] = dividend[j] / divisor[i]; //Time complexity=m^2
        }
    }
}

Работая в обратном направлении, вы можете увидеть, что внутренний оператор займет O(m^2), а поскольку оператор if каждый раз занимает одно и то же количество времени, его временная сложность равна O(1). Тогда ваш окончательный ответ будет O(n^2m^2). Поскольку деление занимает так мало времени на современных процессорах, оно обычно оценивается как O(1) (см. of-the-division-operation" rel="nofollow">this для лучшего объяснения того, почему это так), то, что ваш профессор, вероятно, ищет O (n ^ 2) для второй функции.

Оба O(N²). Вы обрабатываете N² элементов в худшем случае.

Второй пример может быть просто O(N) в лучшем случае (если второй аргумент состоит из нулей).

Я не уверен, как вы получаете другие полиномы. Обычно точная сложность значения не имеет (именно при работе с языком более высокого уровня).

Обозначение Big O или временная сложность описывает взаимосвязь между изменением размера данных (n) и величиной времени/пространства, необходимого данному алгоритму для его обработки.

В вашем случае у вас есть две петли. Для каждого числа n (внешний цикл) вы обрабатываете n элементов (во внутреннем цикле) элементов. Таким образом, у вас есть O(n²) или "квадратичная" временная сложность.

Таким образом, для небольших чисел n разница незначительна, но для больших чисел n она быстро сходит на нет.

Исключение 0 из делителя, как в алгоритме 2, существенно не меняет временную сложность, потому что проверка того, является ли число = 0 равным O(1) и на несколько порядков меньше, чем O(n²) . Устранение внутреннего цикла в этом конкретном случае по-прежнему занимает O(n), и время, необходимое для выполнения O(n²), по-прежнему незначительно. Таким образом, ваш второй алгоритм технически становится (в лучшем случае) O (n) (если в ряду делителей есть только нули).