이 알고리즘이 선형입니까?

이 알고리즘이 선형입니까?

다음 두 가지 질문에서 영감을 얻었습니다.문자열 조작: "접미사를 가진 문자열의 유사성"을 계산하고, C에서 I/P 크기가 5 이상 증가함에 따라 프로그램 실행이 달라지며, 다음과 같은 알고리즘을 생각해 냈습니다.

질문은.

1. 맞습니까, 아니면 제가 추리를 잘못한 것입니까?
2. 알고리즘의 최악의 경우 복잡성은 무엇입니까?

먼저 약간의 문맥이 있습니다.두 문자열의 유사성을 두 문자열의 가장 긴 공통 접두사 길이로 정의합니다.문자열의 완전 자기 유사성은 모든 접미사와 s의 유사성의 합입니다.예를 들어, 아바캅의 총 자기 유사성은 6 + 0 + 1 + 0 + 2 + 0 = 9이고, 반복되는 자기 유사성의 총 자기 유사성은n는.n*(n+1)/2.

알고리즘에 대한 설명:이 알고리즘은 문자열의 접두사 테두리가 중심 역할을 한다는 점에서 Knuth-Morris-Pratt 문자열 검색 알고리즘을 기반으로 합니다.

요약하자면, 문자열의 경계는 s의 적절한 부분 문자열 b이며, 이는 동시에 s의 접두사이자 접미사입니다.

비고: b와 c가 c보다 짧은 s의 경계를 주의하면 b도 c의 경계가 되고, 반대로 c의 모든 경계도 s의 경계가 됩니다.

길이 n의 문자열이 되고 길이 i의 s 접두사가 되는 p가 됩니다.우리는 만약 둘 중 하나라도 확장할 수 없는 폭 k의 경계 b를 부릅니다.i == n아니면s[i] != s[k], 합니다()).k+1s의 접두사는 다음 길이의 테두리입니다.i+1s)의 접두사.

s의 가장 긴 공통 접두사와 접미사가 다음과 같이 시작하는 경우s[i], i > 0, 는 길이 k를 가지며, s의 길이 k 접두사는 s의 길이 i+k 접두사의 extens 불가능한 경계입니다.모래의 일반 접두어이기 때문에 국경입니다.s[i .. n-1] 긴 접두사는

반대로, s의 길이 i 접두사의 (길이 k의) 모든 확장 불가능한 경계는 s와 접미사로 시작하는 가장 긴 공통 접두사입니다.s[i-k].

따라서 우리는 s의 길이 i 접두사의 모든 확장 불가능한 경계의 길이를 합함으로써 s의 전체 자기 유사성을 계산할 수 있습니다.1 <= i <= n 위해서. 그러기 위해서는

1. 표준 KMP 전처리 단계로 접두사의 가장 넓은 경계의 너비를 계산합니다.
2. 접두사의 확장할 수 없는 가장 넓은 테두리의 너비를 계산합니다.
3. 각각의 i에 대하여,1 <= i <= n,한다면p = s[0 .. i-1]비어 있지 않은 extens 불가능한 경계가 있습니다. b를 이 중 가장 넓다고 가정하고 b의 비어 있지 않은 모든 경계 c에 대해 b의 너비를 추가하고, p의 extens 불가능한 경계인 경우에는 그 길이를 추가합니다.
4. 위에서 다루지 않으니 s의 길이 n을 더하세요.

코드(C):

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/*
 * Overflow and NULL checks omitted to not clutter the algorithm.
 */

int similarity(char *text){
    int *borders, *ne_borders, len = strlen(text), i, j, sim;
    borders = malloc((len+1)*sizeof(*borders));
    ne_borders = malloc((len+1)*sizeof(*ne_borders));
    i = 0;
    j = -1;
    borders[i] = j;
    ne_borders[i] = j;
    /*
     * Find the length of the widest borders of prefixes of text,
     * standard KMP way, O(len).
     */
    while(i < len){
        while(j >= 0 && text[i] != text[j]){
            j = borders[j];
        }
        ++i, ++j;
        borders[i] = j;
    }
    /*
     * For each prefix, find the length of its widest non-extensible
     * border, this part is also O(len).
     */
    for(i = 1; i <= len; ++i){
        j = borders[i];
        /*
         * If the widest border of the i-prefix has width j and is
         * extensible (text[i] == text[j]), the widest non-extensible
         * border of the i-prefix is the widest non-extensible border
         * of the j-prefix.
         */
        if (text[i] == text[j]){
            j = ne_borders[j];
        }
        ne_borders[i] = j;
    }
    /* The longest common prefix of text and text is text. */
    sim = len;
    for(i = len; i > 0; --i){
        /*
         * If a longest common prefix of text and one of its suffixes
         * ends right before text[i], it is a non-extensible border of
         * the i-prefix of text, and conversely, every non-extensible
         * border of the i-prefix is a longest common prefix of text
         * and one of its suffixes.
         *
         * So, if the i-prefix has any non-extensible border, we must
         * sum the lengths of all these. Starting from the widest
         * non-extensible border, we must check all of its non-empty
         * borders for extendibility.
         *
         * Can this introduce nonlinearity? How many extensible borders
         * shorter than the widest non-extensible border can a prefix have?
         */
        if ((j = ne_borders[i]) > 0){
            sim += j;
            while(j > 0){
                j = borders[j];
                if (text[i] != text[j]){
                    sim += j;
                }
            }
        }
    }
    free(borders);
    free(ne_borders);
    return sim;
}


/* The naive algorithm for comparison */
int common_prefix(char *text, char *suffix){
    int c = 0;
    while(*suffix && *suffix++ == *text++) ++c;
    return c;
}

int naive_similarity(char *text){
    int len = (int)strlen(text);
    int i, sim = 0;
    for(i = 0; i < len; ++i){
        sim += common_prefix(text,text+i);
    }
    return sim;
}

int main(int argc, char *argv[]){
    int i;
    for(i = 1; i < argc; ++i){
        printf("%d\n",similarity(argv[i]));
    }
    for(i = 1; i < argc; ++i){
        printf("%d\n",naive_similarity(argv[i]));
    }
    return EXIT_SUCCESS;
}

자, 이게 맞습니까?그렇지 않다면 차라리 놀라겠지만, 전에 틀렸던 적이 있어요.

알고리즘의 최악의 경우 복잡성은 무엇입니까?

O(n)이라고 생각하지만, 접두사가 확장할 수 없는 가장 넓은 경계에 포함될 수 있는 확장 가능한 경계의 수가 경계를 이루었다는 증거를 아직 찾지 못했습니다(또는 그러한 발생의 총 수가 O(n)).

나는 날카로운 경계에 가장 관심이 있지만, 만약 당신이 그것이 예를 들어 O(n*log n) 또는 O(n^(1+x))임을 증명할 수 있다면,x, 그것은 이미 좋습니다.(그것은 분명히 최악의 2차적이기 때문에, "It's O(n^2)"라는 대답은 2차적이거나 거의 2차적인 행동에 대한 예를 동반하는 경우에만 흥미롭습니다.)

이것은 정말 깔끔한 생각처럼 보이지만 슬프게도 저는 최악의 행동이 O(n^2)라고 생각합니다.

다음은 반례에 대한 저의 시도입니다. (저는 수학자가 아니므로 제 생각을 표현하기 위해 방정식 대신 파이썬을 사용한 것을 용서해주세요!)

4K+1 기호를 가진 문자열을 고려합니다.

s = 'a'*K+'X'+'a'*3*K

이거는.

borders[1:] = range(K)*2+[K]*(2*K+1)

ne_borders[1:] = [-1]*(K-1)+[K-1]+[-1]*K+[K]*(2*K+1)

참고:

1) ne_borders[i]는 i의 (2K+1) 값에 대해 K와 같습니다.

2) 0<=j<=K일 경우, 경계[j]=j-1

3) 알고리즘의 최종 루프는 i의 2K+1 값에 대해 j==K로 내부 루프로 들어갑니다.

4) 내부 루프는 j를 0으로 줄이기 위해 K번 반복합니다.

5) 따라서 알고리즘이 길이 N의 최악의 경우 문자열을 수행하려면 N*N/8 이상의 연산이 필요합니다.

예를 들어, K=4의 경우 내부 루프를 39번 돌게 됩니다.

s = 'aaaaXaaaaaaaaaaaa'
borders[1:] = [0, 1, 2, 3, 0, 1, 2, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4]
ne_borders[1:] = [-1, -1, -1, 3, -1, -1, -1, -1, 4, 4, 4, 4, 4, 4, 4, 4, 4]

K=2,248의 경우 내부 루프를 10,111,503회 돌게 됩니다!

혹시 이 경우의 알고리즘을 수정할 수 있는 방법이 있을까요?

Z-알고리즘을 보고 싶을 수도 있습니다. 선형일 가능성이 있습니다.

s는 길이 N의 C 문자열입니다.

Z[0] = N;
int a = 0, b = 0;
for (int i = 1; i < N; ++i)
{
  int k = i < b ? min(b - i, Z[i - a]) : 0;
  while (i + k < N && s[i + k] == s[k]) ++k;
    Z[i] = k;
  if (i + k > b) { a = i; b = i + k; }
}

이제 유사성은 단지 Z의 입력의 합일 뿐입니다.

언급URL : https://stackoverflow.com/questions/8563336/is-this-algorithm-linear