データ構造とアルゴリズム学習ノート(一)いくつかの低時間複雑度のアルゴリズム
2909 ワード
いくつかの低時間複雑度アルゴリズム:
(1)最大サブシーケンスと問題所与の整数A[0]~A[N-1]は、負の数がある可能性があり、SUM(k=i;j)A[k]の最大値を求める.
時間複雑度はO(N)のみ
(2)ユークリッドアルゴリズム:最大公因数を計算して2つの整数の最大公因数を求める.
時間複雑度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
時間複雑度O(logN)実際にはN=1のこのコードも省略できるが,N=1の場合,最後の行で同様の作業が行われているためである.
(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の場合,最後の行で同様の作業が行われているためである.