Я пишу простой алгоритм для сравнения, если два вектора 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. Отношение в приведенном выше графике далеко от прогнозируемого. Почему это?
