[강의] 11월 20일 수업정리

오늘은 빅오 데이터와 버블 정렬에 대한 수업을 들었다.

1. 빅 오 데이터

1.1 빅오(Big-O)의 의미

• 시간 복잡도(Time Complexity): 알고리즘이 실행되는 속도를 표현. 가장 많은 작업(연산)을 요구하는 반복문의 구조를 기준으로 측정.
  예를 들어, 반복문의 횟수와 데이터 크기의 관계를 따진다.

 

1.2 주요 빅오(Big-O) 표기법

• O(1): 데이터 크기에 관계없이 항상 일정한 작업을 수행 (예: 단순 변수 접근).
• O(n): 데이터의 크기(n)에 비례하여 작업이 늘어남 (예: 단일 반복문).
• O(log n): 데이터 크기를 반복적으로 반으로 나누는 방식 (예: 이진 탐색).
  • 데이터의 개수를 반씩 줄이는 방식이므로, 데이터 크기(n)가 2배가 되면 작업 횟수는 한 번만 증가.
• O(n²): 이중 반복문처럼 데이터 크기(n)의 제곱에 비례하여 작업이 늘어남.
• O(2ⁿ): 데이터 크기에 따라 작업량이 지수적으로 증가 (예: 모든 부분집합을 탐색)

 

1.3 log n의 의미

• log n은 데이터 크기를 반으로 나누는 연산이 몇 번 반복되는지를 의미.
• 예: 데이터 크기가 16일 때, 이를 반씩 나누면 16 → 8 → 4 → 2 → 1로 총 4회 반복.
  즉, log₂(16) = 4.
• 데이터 크기(n)가 커질수록 연산 횟수 증가가 완만함.

 

1.4 공간 복잡도(Space Complexity)

• 메모리 사용량을 측정. 알고리즘 실행 중 얼마나 많은 메모리를 사용하는지 확인.
• 게임 업계에서는 속도를 높이기 위해 메모리를 효율적으로 사용하지 않는 경우가 많음.
  (예: 캐싱을 활용하여 계산을 줄이거나, 미리 데이터를 저장해 속도를 증가).
• 하지만, 메모리가 제한적인 환경(임베디드 시스템, 모바일 등)에서는 공간 복잡도가 중요.
  따라서 공간 복잡도의 개념은 알고 있어야 함.

 

1.5 정리된 포인트

• 시간 복잡도는 속도를 측정하며, 반복문의 구조(횟수 관계)를 따짐.
• log n은 데이터를 반으로 나누는 과정을 곱셈적으로 반복할 때 발생.
• 공간 복잡도는 메모리 사용량을 측정하며, 게임 업계에서는 속도를 중시하여 덜 신경 쓰지만, 다른 업종에서는 중요한 요소가 될 수 있음.

2. 버블 정렬

 

2.1 핵심

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환을 하는 방식이다.
• 즉, 버블 정렬은 첫 번째 자료와 두번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, .. 이런 식으로 마지막 - 1 번째자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다.

#include <iostream>

void bubbleSortLogic(int* pData, int nLength);
void bubbleSort(int* pData, int nLength);
void swapData(int& nDst, int& nSrc);
void printData(const int* pData, int nLength);

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

	bubbleSort(arData, 6);
	printData(arData, 6);
}

void bubbleSortLogic(int* pData, int nLength)
{
	for (int i = 0; i < nLength - 1; i++)
	{
		if (pData[i] > pData[i + 1])
			swapData(pData[i], pData[i + 1]);
	}
}

void bubbleSort(int* pData, int nLength)
{
	while (nLength > 1)
	{
		bubbleSortLogic(pData, nLength);
		nLength--;
	}
}

void swapData(int& nDst, int& nSrc)
{
	int nTmp = nDst;
	nDst = nSrc;
	nSrc = nTmp;
}

void printData(const int* pData, int nLength)
{
	for (int i = 0; i < nLength; i++)
	{
		printf("%d ", pData[i]);
	}
	printf("\n");
}