데이터 구 조 를 정리 하 는 노트 (1)

데이터 구 조 를 정리 하 는 노트 (1)
1. 데이터 구조의 부분 적 인 깔개

컴퓨터 과학 에서 특별한 성명 이 없 으 면 모든 대 수 는 2 를 밑 으로 한다.

로그 의 기본 공식: logAB = (logcb)/(logcA).

모 연산: N 이 A - B 를 제거 하면 A 와 B 모 N 이 같 고 A. 1. B (mod N) 로 기록 합 니 다. 예: 81. 1. 61. 1 (mod 10). A. 1. B (mod N) 라면 A + C. 1. B + C (mod N) AD. 1. BD (mod N)

재 귀 약 론: 한 함수 가 자신 으로 정의 할 때 재 귀 라 고 부른다.C. 함수 재 귀 를 허용 합 니 다.예:

int F(int x )
                   {
                       If(x==0)
                           return 0;
                       else
                           return 2*F(x-1)
                   }

C 의 재 귀 함수 가 기준 이 없 으 면 의미 가 없다.예 에서 의 기준 상황 은 F (0) = 0. 재 귀적 인 네 가지 기본 법칙: (1) 기준 상황 (base case) 이다.너 는 반드시 어떤 기준 적 인 상황 이 있어 야 한다. 그것들 은 귀속 하지 않 아 도 해답 을 구 할 수 있다.(2) 끊임없이 추진 (making progress).재 귀적 으로 해결 해 야 할 상황 에 대해 재 귀적 호출 은 반드시 기준 상황 이 발생 하 는 방향 으로 추진 해 야 한다.(3) 설계 법칙.모든 재 귀 호출 이 가능 하 다 고 가정 하 세 요.(4) 합성 효과 법칙 (compound interest rule).한 문제 의 같은 실례 를 풀 때, 서로 다른 귀속 호출 에서 중복 적 인 작업 을 하지 마 십시오.(이해 해 야 할) 수의 재 귀 인쇄 알고리즘 (N > = 0):

 void  PrintOut( unsigned int N )
                           {  
                               if( N >= 10)
                                   PrintOut( N / 10);
                               PrintDigit( N % 10);
                          }      （     ）

2. 수학 기초

정의: 정상 수 c 와 n0 이 존재 하면 N > = n0 시 T (N) < = cf (N) 가 있 으 면 T (N) = O (f (N) 로 기록 합 니 다.즉 T (N) 의 성 장 률 이 f (N) 와 같은 성 장 률 보다 작 다 는 것 이다.예 를 들 어 1000 N = O (N * * 2). 이런 기법 을 대 오기 법 이 라 고 부른다.

정의: 정상 수 c 와 n0 이 존재 하면 N > = n0 시 T (N) > = cg (N) 이 있 으 면 T (N) = 오 메 가 (g (N) 로 기록 합 니 다.즉 T (N) 의 성 장 률 이 g (N) 과 같은 성 장 률 보다 크다 는 것 이다.

정의: T (N) =θ(h (N)) 당 하고 T (N) = O (f (N) 와 T (N) = 오 메 가 (g (N) 만 한다.성 장 률 의 크기 가 같다 는 것 이다.

정의: T (N) = o (f (N) 당 하고 T (N) = O (f (N) 당 하고 T (N) ≠θ(h(N)).즉 T (N) 의 성 장 률 이 f (N) 와 의 성 장 률 보다 작 다 는 것 이다.이것 은 소기 법 이다.구별: 없다.

법칙 1: T1 (N) = O (f (N) 와 T2 (N) = O (g (N) 라면

T1(N)+ T2(N) = max(O(f(N)),O(g(N))); T1 (N) * T2 (N) = O (f (N) * g (N). 법칙 2: T (N) 가 k 차 다항식 이면 T (N) =θ(N * * k). 법칙 3: 임 의 상수 k, (log N) * * k = O (N). 즉, 대수 성장 이 매우 느리다.

n 이 무한 해 질 때 f (N)/g (N) 에 한 계 를 구한다.한계 가 0 일 때 f (N) = o (g (N);극한 이 표시 일 때 g (N) = o (f (N));극한 이 c ≠ 0 일 때 f (N) =θ(g(N));극한 이 좌우 로 흔 들 릴 때 두 사람 은 무관 하 다.항상 저급 과 상 수 를 버린다.

운행 시간 계산 (특정한 시간 단위 가 존재 하지 않 음): 전략: 내향 외.법칙 1: for 순환: 한 번 for 순환 의 운행 시간 은 대부분 이 for 순환 내 문장의 운행 시간 에 교체 횟수 를 곱 합 니 다.법칙 2: 포 함 된 for 순환.안에서 밖으로 이 순환 들 을 분석 하 다.순환 내부 에 포 함 된 문장의 전체 운행 시간 은 이 문장의 운행 시간 에 이 그룹의 모든 for 순환 크기 의 곱 하기 입 니 다.예:

 for( i =0;i < N; i++)
{
	for(j=0;j

법칙 3: 순서 문: 각 문장의 운행 시간 을 구 하면 된다 (그 중의 최대 치 는 이른바 운행 시간).예:

for(i=0;i

법칙 4: IF/ELSE 문장: 프로그램 세 션:

if(x)
{
	S1
}
else
{
	S2
}//  if/else                S1 S2              。

최대 하위 서열 에 대한 비교적 좋 은 알고리즘:

int MaxSubsequenceSum(const int A[],int N)
{
	int ThisSum,MaxSum,j;
	ThisSum = MaxSum = 0;
	for(j = 0;j < N;j++)
	{
		ThisSum += A[j];
		if(ThiaSum > MaxSum)
		{
			MaxSum = ThisSum;
		}
		else if(ThisSum < 0)
		{
			ThisSum = 0;
		}
	}
	return MaxSum;
}//        。

실행 시간의 대수: 하나의 알고리즘 이 상수 시간 (O (1) 으로 문제 의 크기 를 그 중의 일부분 (보통 1/2) 으로 줄 이면 이 알고리즘 은 O (logN) 입 니 다.상수 시간 을 사용 하여 문 제 를 상수 만 줄 이면 이 알고리즘 은 O (N) 의 것 이다.

첫 번 째 데이터 구조 실현 방법: 대 분 검색

함수 부분:

int BinarySearch(const ElementType A[],ElenentType X,int N)
{
	int Low,Mid,High;
	Low = 0;
	High = N-1;
	while(Low <= High)
	{
		Mid = ( Low + High) / 2;
		if(A[Mid] < X)
		{
			Low = Mid + 1;
		}
		else if(A[Mid] > X)
		{
			High  = Mid + 1;
		}
		else 
		   return Mid;
	}
	return -1;
 } //     O(logN)。

10. 유클리드 알고리즘 (두 정수 의 최대 공약수 계산): Gcd (M, N) [이때 M > = N, M

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

11. 정리: M > N 이면 M mod N < M/2.

데이터 구 조 를 정리 하 는 노트 (1)

좋은 웹페이지 즐겨찾기