Помощь с простым алгоритмом

Question

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

поэтому первый вопрос у меня есть,

Prefix-Match(T[1..n], P[1..m]) { 
i := 1 // point to current position in T[] 
while(i <= n) { 
// find a match for first character of P 
while(i <= n && T[i] != P[1]) i++ 
if (i > n) return; // quit 
len := 1 
// match as much as possible 
while(len < m && i+len <= n && T[i+len] == P[1+len]) len++ 
output i, len 
i++ 
} 

что бы выход этой программы, если Т = [а, Ь, а, б, в, а, Ь] и Р = [а , Ь, а] ???

и, во-вторых, как мне решить временную сложность алгоритма в терминах m и n?

Answer 1

Ну, в первую очередь, вопрос: в какой книге вы говорите? Если это именно пример кода из него, то это должно быть ужасно ...

И теперь для ответа:

• эта функция проходит через каждый элемент Т (это первая while петля),
• , то он находит первое вхождение первого элемента Р в диапазон от «i» до конца таблицы T. В этом случае i = 1, так как T[1] == P[1] (если T не содержит первый элемент P, то функция просто возвращается),
• , тогда он просматривает, сколько элементов в T, начиная с i, соответствуют последующим элементам в P (это означает, что он будет принимать элемент T[i+1] и проверить, соответствует ли это P[2] и то же самое с T[i+2] и P[3])
• тогда печатает i он нашел и сколько матчей он нашел.

В основном эта функция находит все подмножества T, которые соответствуют P. И точный результат должен выглядеть следующим образом:

1, 3 
3, 2 
6, 2 

Tldr: первое число является показателем, при котором элемент P[1] находится в таблица T и второе число - это число элементов, следующих за ним, равное его аналогам в таблице P.

Но я не знаю, каково было намерение автора - из того, что я понимаю, найденное подмножество не обязательно полностью соответствуют набору P, т. е. если взять: T = [a,c,a] и P = [a,b,a] мы все равно получили бы результат 1,3. Нет элемента, который разбивает цикл, если последующий элемент найденного подмножества в T отличается от его аналога в P.

О сложности времени в Интернете много статей. Если вы хотите получить книгу, то я буду использовать CLRS Введение в Алгоритмы или Руководство по разработке алгоритмов.

Answer 2

что бы выход этой программы будет Т = [а, Ь, а, б, с, а, б] и P = [A, B, A] ???

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

Например, если начать с Т и Р, как указано выше, вы должны сначала установить значения для Т, п, Р и т пройти через i := 1 записи 1 в слот для i, то вы бы пройти через while(i <= n) {, потому что (1 < n) и т. д.

Когда вы сделаете это несколько раз, вы сможете сделать это намного быстрее.

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

поэтому первый вопрос у меня есть,

Prefix-Match(T[1..n], P[1..m]) { 
    i := 1 // point to current position in T[] 
    while(i <= n) { 
    // find a match for first character of P 
    while(i <= n && T[i] != P[1]) i++ 
    if (i > n) return; // quit 
    len := 1 
    // match as much as possible 
    while(len < m && i+len <= n && T[i+len] == P[1+len]) len++ 
    output i, len 
    i++ 
} 

что бы выход этой программы будет Т = [а, Ь, а, б, в, а, Ь] и Р = [а , Ь, а] ???

и, во-вторых, как мне решить временную сложность алгоритма, в условиях m и n?

Я не уверен, вы будете готовы к сложности время тренировки, но думать о том, как т и п влияют на максимальное время, затрачиваемое алгоритмом (или как долго он будет считать вас делать вручную):

• От этого зависит m?
• От этого зависит n?
• Если это зависит от того, является ли это функцией на m+n или больше похожа на m*n? То есть для одного и того же размера T и удвоенного размера P требуется ли в два раза больше?