Оптимальное двоичное дерево поиска Кнута за O (n ^ 2) - PullRequest
Новая
       105

Оптимальное двоичное дерево поиска Кнута за O (n ^ 2)

0 голосов
/ 18 июня 2020

Я пытаюсь реализовать оптимальное двоичное дерево поиска Кнута, которое может работать за время O (n ^ 2). У меня есть код, который выполняется в O (n ^ 3). 

float P[N + 1] = {0, .13, .12, .15, .05, .12, .10, .08, .09, .03, .13};
float sum[N + 1] = {0, .13, .25, .40, .45, .57, .67, .75, .84, .87, 1.00};
float M[N + 1][N + 1];
int root[N + 1][N + 1];
int s, i, j;
float temp;
for (s = 0; s <= N; s++){
    for (i = 0; i <= N; i++){
        M[s][i] = 0;
        root[s][i] = 0;

    }

}
for (s = 2; s <= N; s++){
    for (i = 1; i <= N - s + 1; i++){
        M[s][i] = N;
        for (j = i; j <= i + s - 1; j++){
            temp = M[j - i][i] + M[i + s - j - 1][j + 1]+ sum[i + s - 1] - sum[i - 1] - P[j];
            if (M[s][i] > temp){
                M[s][i] = temp;
                root[s][i] = j;

            }

        }

    }
}

M - это массив затрат. P - вероятность каждого узла. Я почерпнул некоторые идеи из: Dynami c Programming: Почему Кнут усовершенствовал оптимальное двоичное дерево поиска O (n ^ 2)? . В моем случае я пытался изменить третий l oop с for (j = i; j <= i + s - 1; j++) на for (j = root[s+1][i]; j <= root[s][i-1]; j++). Но не работает. Может ли кто-нибудь дать мне ключ к решению этой проблемы?

1 Ответ

0 голосов
/ 19 июня 2020

Предполагается, что вы вычисляете стоимость оптимальных поддеревьев в неубывающем порядке по размеру, поэтому, когда вы заполняете M [s] [i] --- минимальную стоимость поддерева размера s крайний левый ключ которого имеет индекс i - вы еще не заполнили M [s + 1] [i] или root [s + 1] [i].

Ура, Трэвис

PS "j <= root [s] [i-1]" тоже не совсем верно. </p>

...