데이터 구조의 알고리즘 분석

중요 한 결론

만약 \ (T 1 (N) = 0 (f (N) \) 그리고 \ (T 2 (N) = O (g (N) \) 그렇다면 a. \ (T 1 (N) + T 2 (N) = O (f (N) + g (N) \)

b. \(T_1(N) * T_2(N) = O(f(N)*g(N))\)

T (N) 가 k 차 다항식 이면 \ (T (N) = O (N ^ k) \)

    3. 임의의 상수 k 에 대해 \ (log ^ kN = O (N) \)
         대수 성장 이 매우 느리다 는 것 을 나타 낸다.
연산 시간 계산

시간 단원 의 계산

        
                
          i、   i<=N，   i           。                  

    2. 일반 법칙

  1 - for       for            for         （    ）            
  2 -     for               ，                                    for        
  3 -                     ，                   O(N) + O(N^2)       O(N^2)
  4 - if/else        if/else                       S1   S2              。

예 를 들 어 가장 큰 하위 서열 과 네 가지 해법 에 관 한 시간 연산
제 1 종

public static int maxSubSum1(int [] a)
{
 int maxSum = 0; // O(1)
  //           For     O(1)     
 for(int i = 0; i < a.length; i++) //      N
 {
 for(int j = i; j < a.length; j++) //       N - i，   N，       
 {
 int thisSum = 0;
 for(int k = i; k <= j; k++) //       j - i + 1，   N
 thisSum += a[k];
 //    O(1 * N * N * N) = O(N3)
 if(thisSum > maxSum)
 maxSum = thisSum; //    +         O(N2)
 }
 }
 return maxSum;
}

알고리즘 실행 시간 은 \ (O (N ^ 3) \)
두 번 째

public static int maxSubSum2(int [] a)
{
 int maxSum = 0; // O(1)
 // 2  for   ，T = O(1 * N * N) = O(N2)
 for(int i = 0; i < a.length; i++)
 {
  int thisSum = 0;
 for(int j = i; j < a.length; j++)
 {
 thisSum += a[j];
 if(thisSum > maxSum) // O(N2)
 maxSum = thisSum;
 }
 }
 return maxSum;
}

알고리즘 실행 시간 \ (O (N ^ 2) \)
제3 종
나 누 어 다스리다

private static int maxSumRec(int [] a, int left, int right)
{
 if(left == right) // Base case
 if(a[left] > 0)
 return a[left]
 else
 return 0;
 int center = (left + right) / 2;
 //           N / 2       （   N    )
 //          T(N / 2)     ，    2T(N/2)      
 int maxLeftSum = maxSumRec(a, left, center);
 int maxRightSum = maxSumRec(a, center + 1, right);
  //      For  ，              
 // O(1) * 4 + O(N) * 2 ≈ O(N)
 int maxLeftBorderSum = 0, leftBorderSum = 0;
 for(int i = center; i >= left; i--)
 {
 leftBorderSum += a[i];
 if(leftBorderSum > maxLeftBorderSum)
 maxLeftBorderSum = leftBorderSum;
 }
 int maxRightBorderSum = 0, rightBorderSum = 0;
 for(int i = center + 1; i <= right; i++)
 {
 rightBorderSum += a[i];
 if(rightBorderSum > maxRightBorderSum)
 maxRightBorderSum = rightBorderSum
 }
 return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRightBorderSum); //        
}
public static int maxSubSum3(int []a)
{
 return maxSumRc(a, 0, a.length - 1);
}

알고리즘 실행 시간 2T (N / 2) + O (N)
네 번 째

public static int maxSubSum4(int [] a)
{
 int maxSum = 0, thisSum = 0;
  for(int j = 0; j < a.length; j++) // O(N)
 {
 thisSum += a[j];
  if(thisSum > maxSum) // O(logN)
 maxSum = thisSum;
 else if(thisSum < 0)
 thisSum = 0;
 }
 return maxSum;
}

알고리즘 실행 시간 O (Nlog N)
실행 시간의 로그
일반 법칙

           (O(1))             (    1 / 2)，        O(log N)。    ，                      (      1),          O(N) 。

그 특징 을 지 닌 세 가지 예

반값 으로 찾기

public sttatic>
int binarySearch(AnyType [] a, AnyType x)
{
 int low = 0, high = a.length - 1;
 while(low <= high)
 {
 int mid = (low + high) / 2;
  // a[mid] < x   
 if(a[mid].compareTo(x) < 0)
 low = mid + 1;
 else if (a[mid].compareTo(x) > 0)
 high = mid - 1;
 else
 return mid; // found
 }
 return NOT_FOUND; // NOT_FOUND IS defined as -1;
}

유클리드 알고리즘

public static long gcd(long m, long n)
{
 while(n != 0)
 {
 long rem = m % n;
 m = n;
 n = rem;
 }
 return m;
}

두 정수 의 최대 공약수 (gcd) 는 두 자 를 동시에 제거 하 는 최대 정수 이다.

멱 연산

public static long pow(long x, int n)
{
 if(n == 0)
 return 1;
 if(n == 1)
 return x;
 if(isEven(n))
 return pow(x * x, n / 2);
 else
 return pow(x * x, n / 2) * x;
}