Как найти формулу лучшего и худшего случая моего алгоритма?

Question

Мне дали задание. Напишите алгоритм, чтобы при вводе двух списков данных был хотя бы один общий.

Итак, это мой алгоритм: (я пишу код в php)

$arrayA = array('5', '6', '1', '2', '7');
$arrayB = array('9', '2', '1', '8', '3');
$arrayC = array();

foreach($arrayA as $val){
    if(in_array($val, $arrayB)){
        array_push($arrayC, $val);
    }
}

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

Примечание. Пожалуйста, дайте мне знать, если мой алгоритм неверен. Моя цель - «ввод двух списков данных, которые будут иметь хотя бы один общий».

Answer 1

Для начала:

1. У вас есть явные циклы? Если да, сколько раз они будут работать (max, min, avg)?
2. Есть ли у вас неявные петли? Если да, сколько раз они будут работать (max, min, avg)?
3. Являются ли какие-либо из этих циклов вложенными? Если так, они зависят друг от друга? От чего они зависят

Answer 2

При решении подобных алгоритмических задач вы должны рассматривать списки с «алгоритмической» точки зрения. То есть тип данных с небольшим набором поддерживаемых операций O (1). Обычно, как показано ниже:

• проверить, если список пуст
• добавить элемент в конец списка
• получить первый элемент списка
• удалить первый элемент из списка

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

Будьте очень осторожны при написании кода на развитых языках программирования вместо написания алгоритма, поскольку он скрывает сложность (@FrustratedWithFormsDesign уже намекает на это).

Answer 3

Наихудший случай можно найти, если предположить, что оба списка имеют общий элемент и он является последним в каждом списке: это приведет к прохождению первого списка путем проверки всех элементов второго (вы используете in_array но предположим, что вы делаете это вручную, это одно и то же O(m): сложность).

То есть вы проходите n раз по второму списку, сложность будет O(n*m), где n - длина первого списка, а m - длина второго ..

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