23.01.25 - 시간 복잡도, 이차원 배열과 포인터, 함수 포인터

시간복잡도

입력값에 따라 연산을 할 때 시간이 얼마만큼 걸리는지 표현한 것

 

Big-O 표기법

시간복잡도를 표현할 때 가장 많이 사용하는 방법으로 최악의 경우를 고려해 실행 시간을 계산한다.

최선을 고려하는 빅 오메가,  평균을 고려하는 빅 세타도 있다.

 

Big-O로 표기하는 방법은 먼저 식에서 차수가 가장 큰 것만 남기고

계수도 제외하고 차수만 표기하면 된다.

ex) 3n^3 + 2n^2 + 1 => O(n^3)

 

상수 시간 복잡도 O(1)

개수가 아무리 많아져도 처리하는 시간은 같다.

 

로그 시간 복잡도 O(logN)
요소의 개수가 적을 때 더 빠르고 개수가 많아져도 일정 지점에서 처리하는 시간이 더 커지지 않기 때문에 효율이 좋은편

선형 시간 복잡도 O(N)
요소의 개수가 많아질수록 정비례로 처리 시간이 길어짐

지수 시간 복잡도 O(N^2)
요소의 개수가 많아질수록 기하급수적으로 처리 시간이 길어짐 (지수의 차수가 커질수록 더 심해짐)

 

 

 

void func(int* iParam)
{
	...
}

void main()
{
	int iArr[5] = {1, 2, 3, 4, 5};
    int iArr2[2][5] = {{1, 2, 3, 4, 5}, {1, 2, 3, 4, 5}};
    
    func(iArr);			//(o)
    func(iArr2); 		//(x)
}

 

배열을 매개변수로 받을 때 일차원 배열은 int* 형의 매개변수로 사용하는 것이 가능하지만 이차원 배열은 불가능하다.

형이 맞지 않기 때문인데 이차원 배열을 매개변수로 받으려면 자료형 (*변수명) [열의 개수] 형식으로 써야 한다.

(변수명에 괄호를 붙이지 않으면 포인터 배열이 되버리니 주의!)

 

void func (int (*iParam)[5] ) //열의 크기가 5인 이차원 배열을 매개변수로 받는 함수

 

이렇게 쓰는 이유는 iArr이 요소의 자료형이 int이고 열의 크기가 5인 배열을 가리키는 포인터이기 때문이다.

이차원 배열의 경우 열의 크기를 넘어가면 다음 행으로 넘어가야 하기 때문에 이런식의 표기를 한다.

 

void main(void)
{
	int		iArray[2][3] = {
		{ 1, 2, 3 },
		{ 4, 5, 6 }
	};

	cout << iArray << endl;				//00B3F7E4
	cout << iArray[0] << endl;			//00B3F7E4
	cout << &iArray[0][0] << endl;			//00B3F7E4

	cout << sizeof(iArray) << endl;			//24
	cout << sizeof(iArray[0]) << endl;		//12
	cout << sizeof(&iArray[0][0]) << endl;		//4

	cout << iArray << endl;				//00B3F7E4
   	 cout << *iArray << endl;			//00B3F7E4
	cout << *(*iArray) << endl;			//1
	cout << *(iArray[0]) << endl;			//1
	cout << (&iArray[0]) << endl;			//00B3F7E4
}

 

iArray, iArray[0], &iArray[0][0] 의 값은 모두 이차원 배열 iArray의 시작 주소로 같다.

하지만 size가 iArray는 배열 전체, iArray는 배열의 첫번째 열에 해당하는 크기, &iArray[0][0]은 한 요소에 해당하는 크기다.

 

iArray와 *iArray가 둘 다 배열의 시작점 주소값을 갖고 있다. 이게 많이 헷갈렸는데

iArray는 int(*)[5]형의 포인터지만 배열의 시작점을 가리키고 있고 

*iArray는 iArray[0]인데 역시 배열의 시작점을 가리키므로 값이 같다.

그래서 *(*iArray)로 *을 두 번 붙여줘야 요소값이 나오는 것이다.

 

&iArray[0]은 배열의 시작점을 가리키는 주소 iArray[0]에 &을 붙였는데 

원래라면 성립이 안되지만 C++에서 배열 이름에 &을 붙여도 배열 그 자체를 가리키는 것과 같게 만들어놔서 성립한다.

자세한 내용은 soen.kr C문법 11장 &ar 부분 참조.

 

 

 

함수 포인터

함수의 이름(주소)을 저장하기 위한 포인터이다.

반환 타입 (*변수명) (매개 변수)

 

	int		iTest = 0, iTemp = 0, iResult = 0;

	int		iInput = 0;

	cout << "두 개의 값 입력 : ";
	cin >> iTest >> iTemp;

	cout << "1. 덧셈 2. 뺄셈 3. 곱셈 4. 나눗셈 : ";
	cin >> iInput;

	int(*pFunc[4])(int, int) = { Add, Minus, Mul, Div };

	cout << "연산 결과 : " << pFunc[iInput - 1](iTest, iTemp) << endl;

 

함수 포인터를 이용해 간단한 사칙 연산을 하는 예제이다.