Зависит ли временная сложность кода от циклов или количества операций?

Question

Я делал код, в котором мне нужно было сравнить элементы моего массива с другим массивом.

Но я думал, что это увеличит мою временную сложность с O (n) до O (n ^ 2).), как это уже было внутри цикла for, для первого массива.

Итак, я создал такой код внутри родительского цикла for (с параметром i):

int m = 0;
int ele = array2[m];
if(array1[i] == ele)
    count++;
m++;

Но поскольку то, что делается, то же самое, только я выпустил цикл for, мне было интересно, что сложность по времени действительно была O (n) или стала O (n ^ 2).

Я такжепонимаю, что для этого будут сравниваться только те же проиндексированные элементы и не всеБуду признателен, если кто-нибудь расскажет об этом подробнее.

Answer 1

В этом случае вы всегда сравниваете элемент array[m] (in your case array[0]) с индексом i^th массива array1.Так что это фактически то же самое, что обход одного массива и подсчет количества элементов, соответствующих данному конкретному числу

Сравнение одного массива с другим обычно занимает O (n ^ 2) времени, хотя есть способыделать в меньшее время сложность.Когда-то такое решение может быть O(n+m) time complexity and O(min(n,m)) space complexity.Если вы пересекаете массив меньшего размера и сохраняете элементы в одной хеш-таблице, то вы пересекаете второй массив, чтобы найти элементы из хеш-таблицы.

Answer 2

Временная сложность алгоритма зависит от того, как вы пишете свои циклы, а также от временной сложности операции, которую вы выполняете в алгоритме.

Если ваш алгоритм состоит из любого количества операций O (1)ваш алгоритм равен O (1).

Если ваш алгоритм состоит из одного или нескольких циклов (не вложенных) от константы до n, сложность времени равна O (n * the_time_complexity_of_the_operation_in_the_loop)

Каждое приведенное ниже утверждение занимает O (1) раз:

int m = 0;
int ele = array2[m];
if(array1[i] == ele)
    count++;
m++;

, так что все это O (1).Этот блок находится внутри цикла for, который проходит по вашему массиву, поэтому временная сложность O (n * 1) = O (n), где n - длина массива.

Вот интуитивно понятный способ думать опочему сложность времени стала менее сложной, когда вы сравниваете только элементы с одним и тем же индексом.

Если вы хотите сравнить каждую возможную пару из двух массивов, сколько там пар?Первый элемент первого массива может образовывать пару с n другими элементами из второго массива. Второй элемент первого массива может образовывать пару с n элементами из второго массива и так далее.В общем, для каждого элемента в первом массиве может быть сформировано n пар.Предполагая, что два массива имеют одинаковую длину, общее количество пар равно n ^ 2.Следовательно, необходимо провести много сравнений, что означает, что сложность по времени равна O (n ^ 2).

Если вы хотите сравнить элементы пар по одному и тому же индексу, сколько пар вы можете иметь?n пар, потому что каждый индекс соответствует ровно 1 паре.Поэтому вам нужно сделать n сравнений, что означает, что временная сложность составляет O (n).

Answer 3

Да Сложность времени зависит от цикла и количества операций, выполняемых в нем.

В вашем случае есть одно присваивание int ele = array2[m] и одна условная проверка if(array1[i] == ele) с двумя приращениями m иcount.

Все операции будут занимать постоянное время и будут зависеть от количества времени выполнения цикла.