Как уменьшить вычислительную сложность этого алгоритма?

Question

У меня есть этот алгоритм:

int x[100001],n,j,k,i;
int maxi=0;

for (i=1; i<n; i++) {
    for (j=i+1; j<=n; j++) {
        bool ok=true;
        for (k=i+1; k<=j; k++) {
            if (x[i]<x[i-1]) {
                ok=false;
            }
        }
        if (ok == true) {
            if (j-i+1 > maxi) {
                maxi = j-i+1;
            }
        }
    }
}
cout << maxi;

Как я могу уменьшить сложность, которая изначально была, очевидно, O(N^3), чтобы сделать алгоритм более эффективным?

Answer 1

ну, насколько я могу понять из этого вопроса, это версия O (n ^ 2) для того, что я предполагаю, что алгоритм делает (плохо) ..

удален внутренний граничный цикл, так как он бесполезен.

int n_squared_FindLongestAscendingSubsequence(int* x, int n)
{
    int j, k, i;
    int maxi = 0;

    for (i = 1; i<n; i++) {
        for (j = i + 1; j <= n; j++) {
            if (x[j]<x[j - 1]) 
            { // found the point where the seq descends
                if (j - i > maxi) // if it is longer then what we found?
                    maxi = j - i;
            }
        }
    }
    return maxi;
}

Другое решение в O (n):

int n_FindLongestAscendingSubsequence(int* x, int n)
{
    int maxi = 0;
    int anchor = 0; // will save the index from where it ascends
    int prev = -2 ^ 31;
    for (int i = 1; i < n; i++)
    {
        if (x[i] < x[i-1])
        { // found a point where the seq descends
            if (i - anchor > maxi) // if it is longer then what we found?
                maxi = i - x[i];
            anchor = i; // no point going to 'anchor+1', because all seq will be shorter untill 'i'.
        }
    }
    return maxi;
}