Простой алгоритм временной сложности Вопрос

Question

Я работаю над заданием для вступительного курса Datamining. Я пытаюсь выяснить временную сложность алгоритма (см. Ниже)? Является ли он линейным / экспоненциальным / логарифмическим / квадратичным / полиномиальным? Любые советы о том, как подойти к такому вопросу, будут высоко оценены

Рассмотрим следующий алгоритм поиска третьего наименьшего элемента в массив:

• Ввод: n, a[1..n] - массив чисел a, а n это его размер, n> = 3
• Вывод: - вернуть 3-е наименьшее число
• Временные переменные: b[1..3], t, i

Код:

b[1] = a[1]
b[2] = a[2]
if b[1] > b[2] then t=b[1]; b[1]=b[2];  b[2]=t
b[3] = a[3]
if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
for (i = 4; i <= n; i = i+1)
  if a[i] < b[3] then b[3] = a[i]
  if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
  if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
return b[3]

Answer 1

Хорошее эмпирическое правило: сколько раз вы циклически повторяете ввод?

Answer 2

Он линейный, поскольку единственный внутренний цикл повторяется не более n раз и выполняет только операции с постоянным временем.

Более конкретно

1. b[1] = a[1]
2. b[2] = a[2]
3. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
4. b[3] = a[3]
5. if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
6. if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
7. for (i = 4; i <= n; i = i+1)
8. | if a[i] < b[3] then
9. | | b[3] = a[i]
10. | | if b[2] > b[3] then t=b[2]; b[2]=b[3]; b[3]=t
11. | | if b[1] > b[2] then t=b[1]; b[1]=b[2]; b[2]=t
12. return b[3]

Строки 1-6 выполняются только один раз и должны иметь постоянное время. В контексте одного прогона цикла for строки 8-11 выполняются только один раз и являются операциями с постоянным временем; которые затем повторяются ~ n-3 раза.

Answer 3

Сложность по времени линейна и составляет O (n). Вы делаете итерацию только один раз, начиная с 4 до n. Таким образом, сложность времени составляет O (n)

Answer 4

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

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