У меня есть следующий вопрос. Дайте тильды приближение для числа массива обращается к следующему кодуСколько адресов доступа к массиву для следующих
for (int i=0; i < n; ++i)
for (int j = i/2; j < i; ++j)
A[i] = B[j] + C[j];
Однако, я не могу понять, сколько именно массив доступы есть, с точки зрения N
И я думал, что ответ будет n^3 - n для A и n^2 для обоих B и C.
Возможно, я нахожусь справа?
Порядок N составляет N^2 для обозначения большого О.
Это связано с 2 вложенными циклами.
Если мы предположим, что не существует компилятор/Jir оптимизации, мы имеем:
1) все массивы имеют одинаковое количество доступов
2) второй для выполняется ~ I/2 раза
3) общая сумма (я = 0, г = п) я/2 = O (N^2) (сумма первых п натуральных чисел)
нет, вы не можете рассчитывать как то
Ваш массив A [] является доступ в то же время, что и B [] и C [], единственное различие заключается в том, что A является доступным j раз по адресу i.
и другие вещи, не n3, вы не можете сделать раз B, вы должны проанализировать как for`s считать сложность
так, первый для выполнения n раз, второй для выполнения n/2 раз
В этом случае у вас есть O(nˆ2/4) или просто O(nˆ2)
OH хорошо, что имеет смысл на самом деле, Единственное, чего я не понимаю, это то, почему вы пошли на 'O (n^2/4)' не должно быть ' O (n^2/2) '? – jroy8
Это происходит потому, что вы работаете с натуральными числами, например, для n = 1 и n = 2. у вас есть 1 взаимодействие во втором цикле .. половина ваших взаимодействий одинакова ... в этом случае (N * N/2)/2 –
Так что п^2 массива обращается к вашей поговорке? – jroy8