[자료구조와 알고리즘] 1주차 개요, 시간 복잡도

https://school.programmers.co.kr/learn/courses/13007/13007-c-%EC%96%B4%EC%84%9C%EC%99%80-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%80-%EC%B2%98%EC%9D%8C%EC%9D%B4%EC%A7%80

해당 글은 프로그래머스 스쿨의 '[C++] 어서와! 자료구조와 알고리즘은 처음이지?' 를 수강하고 쓴 글입니다

1강 자료구조 개요

 

1. 자료 구조

• 자료를 효율적(실행 시간 + 메모리 사용량)으로 이용하기 위한 자료의 저장 방식
• 적합한 자료 구조 선택 ->  효율적인 알고리즘 사용 가능
• 종류: 배열, 연결리스트, 큐, 스택, 트리, 해시 테이블 등

 

2. 알고리즘

• 컴퓨터로 문제를 해결하기 위한 일련의 절차나 방법
• 입력, 출력 (입력은 없을 수도 있다)
• 자연어, 순서도, *의사 코드 (pseudo-code), 프로그래밍 언어 코드 등의 방법

* 의사 코드 (pseudo-code): 자연어보다는 코드스럽지만 특정 언어에 종속되어 있지 않은 코드. =, for, return과 같이 범용적인 명령어만 사용 가능

---

2강(C++ 프로그램 개발 환경 설정)과 3강(코딩 컨벤션)은 생략

---

 

4강 시간 복잡도

 

1. 알고리즘 성능 분석

  가. 주어진 문제를 ‘잘’ 해결하는 ‘좋은’ 알고리즘인지 판단하는 법
1) ‘잘’ 해결하는 법
    - 정확성 테스트 (in 코테)
    - 수학적 귀납법
    - 다양한 테스트 케이스 사용
2) ‘좋은’ 알고리즘인지 판단하는 법
    - 효율성 테스트
    - 알고리즘의 자원(resource) 사용량을 분석: 실행 시간, 메모리 사용량, 통신 용량 등
    - 보통 실행 시간에 대한 분석만 다룸
    - 대용량 입력 데이터에 대한 처리 능력 판단

2. 시간 복잡도

  가. 시간 복잡도 (time complexity)
1) 입력의 크기가 커짐에 따라 연산 시간(연산 횟수)이 얼마나 증가하는지를 근사적으로 표현
    - 연산의 실행 횟수를 입력 데이터의 크기(n)에 관한 함수 형태로 표현
    - 알고리즘을 직접 구현하지 않고도 알고리즘의 효율성을 가늠할 수 있음
2) 실행시간 측정 방법의 한계: 알고리즘을 구현한 프로그램의 실행 시간은 실행 환경 (하드웨어, 운영체제,
     언어, 컴파일러 등)에 따라 달라지므로 절대적인 실행 시간 비교는 성능 파악에 한계가 있음

  나. 빅오 표기법 (big-O notation): O(f(n))
1) 대표적인 시간 복잡도 표현 방법
2) 연산 횟수를 구체적인 수식으로 표현하지 않고, 최고차항의 차수만으로 표현
(e.g.) 4n^2 + 2n + 5 -> O(n^2): 3차 함수 이상의 형태로는 증가하지 않는다
3) *점근 표기법(asymptotic notation)의 한 방법으로 실행 시간의 상한을 표현 *점근 표기법: 입력의 크기가 무한으로 증가하는 경우에 실행시간이 어떠한 비율로 증가하는지 표현

  다. 대표적인 빅오 표기법의 예

  라. 예제

예제 1) O(1)

int middle(int data[], int n)
{
	return data[n / 2]; // n값에 관계없이 1회 연산이 실행: O(1)
}

예제 2) O(n)

int summation(int data[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++) // for 반복문 내부 문장이 n번 실행: O(n)
		sum = sum + data[i]; // 이게 n번 실행 

	return sum;
}

예제 3) O(n)

int variance(int data[], int n)
{
	int sum = 0;
	for (int i = 0; i < n; i++) // for문 1번 
		sum = sum + data[i];

	double mean = (double)sum / n;
	double var = 0.0;

	for (int i = 0; i < n; i++) // for문 2번 총 2n번 실행: O(n)
		var += (data[i] - mean) * (data[i] - mean);

	return (var / n);
}

예제 4) O(n)

int find(int data[], int n, int target)
{
	for (int i = 0; i < n; i++) // 최선의 경우 for 반복문 안의 비교 연산이 1회,
		if (data[i] == target)  // 최악의 경우 n번 실행 : O(n) (평균적으로 1/2*n번)
			return i;

	return -1;
}

예제 5) O(n^2)

void bubble_sort(int data[], int n)
{
	for (int i = n - 1; i > 0; i—) // 이중 for 반복문 내부 문장이 1/2*n(n-1)번 실행: O(n^2)
		for (int j = 0; j < i; j++)
			if (data[j] > data[j+1])
				swap(data[j], data[j + 1]);
}

예제 6) O(n)

int sum(int n)
{
	if (n == 1)	// 	재귀 함수가 n번 호출되고, 함수 내부에 단일 연산만 있음: O(n)
		return 1;

	return n + sum(n - 1); 
}

예제 7) O(2^n)

void func(int n)
{
	if (n == 1) return;

	func(n - 1);   // 재귀 함수가 매번 2번의 새로운 호출을 수행함. func(n)이 1번 호출되면, 
	func(n - 2);   // func(n-1)은 2번 호출되고, func(n-2)는 4번, func(n-3)은 8번 등등으로 호출
					  // = O(2^n)
}

3. 시간 복잡도
  가. 주요 시간 복잡도 증가율 비교