Определение времени выполнения алгоритма для сравнения двух массивов

Question

Я хочу знать, как можно определить время выполнения алгоритма, написанного в псевдокоде, чтобы я мог ознакомиться со временем выполнения.Так, например, как вы узнаете, что такое время выполнения алгоритма, который будет сравнивать 2 массива, чтобы определить, не совпадают ли они?

Array 1 = [1, 5, 3, 2, 10, 12] Array 2 = [3, 2, 1, 5, 10, 12] Таким образом, эти два массива не одинаковы, поскольку они упорядочены по-разному.

Мой псевдокод:

1) установлентекущий указатель на первое число в первом массиве
2) установить второй указатель на первое число во втором массиве
3) в то время как (текущий указатель! = "") сравнить с тем же элементом позиции в другом массиве
4), если(текущий указатель == второй указатель)
переместить текущий указатель на следующее число переместить второй указатель на следующее число

5) иначе (выводить, что массивы не совпадают) конец цикла

ИтакЯ предполагаю, что сначала мой код правильный.Я знаю, что шаг 4 выполняется только один раз, поскольку требуется только 1 совпадение, чтобы отображаемые массивы не совпадали.Таким образом, шаг 4 занимает только постоянное время (1).Я знаю, что шаги 1 и 2 также выполняются только один раз.

, насколько я знаю, время выполнения 3 +?(? время выполнения самого цикла)

Теперь я потерялся в части цикла.Выполняется ли цикл n раз (n - это число чисел в массиве?), Поскольку в худшем случае может быть сопоставлено каждое отдельное число?Думаю ли я о правильном времени выполнения?

Если кто-то может помочь с этим, я буду признателен.

Спасибо!

Answer 1

То, о чем вы спрашиваете, называется сложность времени вашего алгоритма. Мы говорим о временной сложности алгоритмов с использованием так называемой записи Big-O .

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

Ваш алгоритм запускается за O(n) время (произносится как "big-oh of n" или "order n" или иногда мы просто говорим "линейное время").

Вы уже знаете, что шаги 1,2 и 4 выполняются с постоянным числом шагов относительно размера массива. Мы говорим, что эти шаги выполняются за O(1) время («постоянное время»).

Итак, давайте рассмотрим шаг 3:

Если в массиве n элементов, то на шаге 3 необходимо выполнить n сравнений в худшем случае . Итак, мы говорим, что шаг 3 занимает O(n) время.

Поскольку на шаге 3 алгоритм занимает O(n) времени, а все остальные шаги выполняются быстрее, мы говорим, что общая временная сложность вашего алгоритма составляет O(n).

Когда мы пишем O(f), где f - некоторая функция, мы имеем в виду, что алгоритм работает с некоторым постоянным коэффициентом f для больших значений.

Взять, к примеру, ваш алгоритм. Для больших значений n (скажем, n = 1000) алгоритм не принимает ровно n шагов. Предположим, что для сравнения требуется 5 инструкций в вашем алгоритме на выбранной вами машине. (Это может быть любое постоянное число, я просто выбираю, например, 5). И предположим, что все шаги 1, 2, 4 выполняются с некоторым постоянным числом шагов каждый, всего 10 инструкций для всех трех из этих шагов.

Тогда для n = 1000 ваш алгоритм будет принимать:

Шаги 1 + 2 + 4 = 10 инструкций. Шаг 3 = 5 * 1000 = 5000 инструкций.

Это всего 5010 инструкций. Это примерно 5 * n инструкций, что является постоянным коэффициентом n, поэтому мы говорим, что это O(n).

Для очень больших n 10 в f = 5*n + 10 становится все более и более незначительным, как и 5. По этой причине мы просто уменьшаем функцию до f is within a constant factor of n for large n, говоря f is in O(n).

Таким образом, легко описать идею о том, что квадратичная функция, такая как f1 = n^2 + 2, всегда больше, чем любая линейная функция, такая как f2 = 10000*n + 50000, когда n достаточно велика, просто записав f1 как O(n) и f2 как O(n^2).

Answer 2

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