[알고리즘] 데이터 구조, 자료 구조 분류, 알고리즘, 성능 분석, 누적합

자료구조 
: '데이터의 저장'을 담당하는 것을 말한다.

분류

선형     구조 ) 리스트 , 큐, 스택

비선형 구조 ) 그래프, 트리

파일    구조 ) 순차 파일, 색인 파일, 직접파일

단순     구조 ) 정수, 실수, 문자, 문자열

 

알고리즘 
: 표현 및 저장된 데이터를 대상으로 하는 '문제 해결 방법'을 말한다. 

성능 분석 2가지 방법

1. 시간 복잡도 : 최적의 시간

주로 빅 O을 이용한다. (빅 오메가도 있다.)

O(1) < O(logn) < O(n) < O(nlogn) < O (n**2) < O(n**3) < O(2**n)

 

참고로 log 밑에 숨겨진 숫자는 10이다.

 

2. 공간 복잡도 : 메모리 분량

 

 

 

 누적합 

강의 두 개를 듣고 정리한 알고리즘이다. 

1. 큰돌

누적합을 이용하면 O(n**n)이 아닌 O(n)의 시간 효율도를 낼 수 있다.

 

2. 오일러

누적합의 정의를 좀 더 알기 쉽게 설명해준다.

 

 

아래는 내가 정리한 누적합의 알고리즘이다.

const arr = [1,2,3,4,5]
const psum = [0]

arr.forEach((_,i) => psum[i+1] = psum[i]+arr[i]);

//psum : (6) [0, 1, 3, 6, 10, 15]

function test(s,e) {
    return psum[s] - psum[e] }

test(5,3) //9