Сравнение экспериментального времени работы алгоритма с теоретическими функциями времени выполнения

Я пишу простой алгоритм для сравнения, если два вектора a1 и a2 целых чисел являются анаграммами (они содержат одни и те же элементы в разных порядках). Например, {2,3,1} и {3,2,1} являются анаграммами, {1,2,2} и {2,1,1} не являются.

Вот мой алгоритм (это очень просто):

1. for ( i = 1; i <= a1.length; i++ )
 1.1. j = i
 1.2. while ( a1[i] != a2[j] )
  1.2.1. if ( j >= a1.length )
   1.2.1.1. return false
  1.2.2. j++
 1.3. tmp = a2[j]
 1.4. a2[j] = a2[i]
 1.5. a2[i] = tmp
2. return true

Представление сравнения двух анаграмм:

Давайте рассмотрим функцию времени выполнения, зависящую от размеров вектора T (n), когда они являются анаграммами в двух ситуациях: pesimistic и average.

• пессимистично

Возникает, когда векторы не имеют повторяющихся элементов, а векторы находятся в обратных порядках.

Кратность в c3, c4 и c6:

Таким образом, конечная функция для пессимистического времени работы:

Уравнение (3) можно записать в более простой форме:

• средний

Возникает, когда векторы не имеют повторяющихся элементов, а векторы находятся в случайных порядках. Критическое предположение здесь состоит в том, что: в среднем мы находим соответствующий элемент из a1 пополам не отсортированного a2 (j/2 в c3, c4 и c6).

Кратность в c3, c4 и c6:

Конечная функция для среднего времени работы:

Написано в более простой форме:

---

Вот мой окончательный вывод и вопрос:

b2 в уравнении (8) в два раза меньше, чем a2 в уравнении (4)

Я прав с (9)?

Я думал, что построение времени работы алгоритма в функции векторных размеров может доказать уравнение (9), но это не так:

На графике видно, что отношение a2/b2 равно 1,11, а не как в уравнении (9), где равно 2. Отношение в приведенном выше графике далеко от прогнозируемого. Почему это?

Ответы

Ответ 1

Я нашел свою проблему!

Это не так, как я думал в предположении для среднего случая: "мы находим соответствующий элемент из a1 пополам не отсортированного a2 (j/2)". Он был скрыт в пессимистическом случае.

Правильный пессимистический сценарий возникает, когда вектор a2 находится в том же порядке, что и a1 со сдвинутым первым элементом до конца. Например:

a1 = {1,2,3,4,5}

a2 = {2,3,4,5,1}

Я измерил экспериментально еще раз время работы моего алгоритма с новым допущением для пессимистического случая. Вот результаты:

Наконец, экспериментальное соотношение для a2/b2: 2,03 +/- 0,09

И это доказательство для моих теоретических функций.

Благодарим всех вас за то, что вы со мной и пытаетесь решить мою тривиальную ошибку!

Ответ 2

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

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