データ構造とアルゴリズム学習ノート(一)いくつかの低時間複雑度のアルゴリズム

いくつかの低時間複雑度アルゴリズム:
(1)最大サブシーケンスと問題所与の整数A[0]~A[N-1]は、負の数がある可能性があり、SUM(k=i;j)A[k]の最大値を求める.

int MaxSubsequenceSum(const int A[];int N){
    int ThisSum=0,MaxSum=0;
    for(int i=0;iif(ThisSum > MaxSum){
            MaxSum = ThisSum;   
        }else if(ThisSum < 0){
            ThisSum = 0;
        }
    }
    return MaxSum;
}

時間複雑度はO(N)のみ
(2)ユークリッドアルゴリズム:最大公因数を計算して2つの整数の最大公因数を求める.

unsigned int GCD(unsigned int M,unsigned int N){
    unsigned int Rem;
    while(N>0){
        Rem = M%N;
        M = N;
        N = Rem;
    }
    return M;
}

時間複雑度O(logn)はMとNのどちらが大きいかの問題を考慮する必要はなく,1回のサイクルでMが大きいNが小さいように調整されるからである.
(3)べき乗演算で整数のN乗を求める一般的な考え方はN−1乗を用いることであり,時間的複雑度はO(N)が再帰アルゴリズムを用いるほうがよい:Nが偶数の場合:xN=xN/2∗xN/2 Nが奇数の場合:xN=x(N−1)/2∗x(N−1)/2∗x

long int Pow(long int x,unsigned int N){
    if(N == 0)
        return 1;
    if(N == 1)
        return x;
    if(N%2 == 0)
        return Pow(x*x,N/2);
    else
        return Pow(x*x,(N-1)/2)*x;
}

時間複雑度O(logN)実際にはN=1のこのコードも省略できるが,N=1の場合,最後の行で同様の作業が行われているためである.