알고리즘 다시 공부하기 1일차

1일차

알고리즘 설계 시에 고민해야 하는 거

1. 알고리즘이 우리가 기대한 결과를 출력하는지
2. 선택한 방법이 최선인지
3. 규모가 더 큰 데이터 셋에도 동작할지

알고리즘의 분류

1. 데이터 집약적 알고리즘 → ex) 대용량에 파일에 적용된 압축 알고리즘
2. 연산 집약적 알고리즘 → ex) 매우 큰 소수를 찾는 알고리즘
3. 1번 + 2번을 한 알고리즘 → 자원 소모 多, 가용한 자원 지능적 할당 필요!

• 데이터 → 크기 + 속도 + 다양성

(속도 기준 : 배치 → 주기적 → 준 실시간 → 실시간 프로세서 순)

• 연산 → 문제를 처리하는데 소요되는 자원에 관련 된것

→ 하려는 일에 따라서 더 많은 처리 능력이 필요로 해짐

성능 분석하기

1. 공간 복잡도 분석 → 알고리즘이 입력데이터를 처리하는데 필요한 메모리양 추정

알고리즘이 돌아가는 과정 : 입력 데이터 처리 할 때 임시로 자료 구조를 메모리에 저장

(알고리즘 설계 방식 : 데이터의 개수, 유형, 크기를 결정 → 알고리즘 실행에 필요한 하드웨어의 메모리 양을 결정)

⇒ 공간 복잡도 분석은 효율적인 설계를 위해 필수적인 것이다.

  2. 시간 복잡도 분석 → 알고리즘의 구조에 따라 할당된 작업을 완료하는데 걸리는 시간을 추정

→ 하드웨어의 성능과는 관계 없이 알고리즘 자체의 구조에만 영향을 받음

⇒ 특정 문제를 여러 알고리즘으로 풀 때 어느 알고리즘이 시간 효율성 측면에서 가장 좋은지

1. 구현 후 프로파일링 분석 방식 : 다양한 후보 알고리즘 구현 - 실행 하여 성능 비교
2. 구현 전 이론적 분석 방식 : 성능을 수학적으로 근사하여 비교 (알고리즘의 구조에만 집중가능)

성능 추정

알고리즘의 성능 → 입력데이터의 유형에 따라 달라짐

IF 입력데이터가 문제맥락에 맞게 정렬? → 알고리즘의 실행 속도 DOWN

입력데이터에 따른 의존성 문제를 해결하는데는 성능 분석 시 여러 경우 고려 필요

👍 최상의 경우 - 알고리즘이 최상의 성능을 내도록 입력 데이터가 정리된 경우

😟 최악의 경우 - 작업을 완료하는데 걸리는 시간이 최대가 되는 경우

→ 대신 이를 분석하여 알고리즘 성능의 하한선 확인 가능

→ 최악의 경우 분석은 대규모 데이터를 포함한 복잡한 문제를 풀때 GOOD

👋 평균의 경우 - 다양한 입력데이터를 그룹별로 분석해 평균을 계산해 분석

어느 알고리즘이 가장 빠른지 아는 방법

→ 시간 복잡도와 빅오 표기법

빅오 표기법

1. 상수 시간 복잡도 0(1)

def getFirstone(myList):
		return myList[0]

1. 선형 시간 복잡도 O(n)

def getSumlist(myList):
		sum = 0
		for i in myList:
			sum += i
		return sum

→일차원 배열에서 요소를 검색하는 작업 or 가장 작은 값을 찾는 작업

1. 이차 시간 복잡도 O(n^2)

def getSumlist(myList):
		sum = 0 
		for i in myList:
				for j in i:
						sum += j
		return sum

→ 이중 for문, 버블 정렬 등등

1. 로그 시간 복잡도 O(logn)

루프를 순회할 때 마다 입력데이터의 크기가 일정한 배수로 줄어드는 경우 → ex) 이진 탐색

⇒ 최악의 성능은 O(n^2) 최고의 성능은 O(logn)