*이 내용은 인프런 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)을 수강하며 정리한 내용입니다.

프로그램

자료구조와 알고리즘으로 이루어져있어.

실력이 있는 사람은 적절한 자료구조를 선택해 적절한 알고리즘으로 원하는 결과를 얻지.

시간복잡도

특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간이야.

하지만 각자의 컴퓨터 성능에 따라 해결하는 시간이 달라지겠지?!

그럼 코드에서 성능에 가장 많은 영향을 주는 부분은 어떤 것일까?

바로 반복문이야. 따라서 해당 알고리즘의 반복문을 보고 성능을 평가해 😀

예를 들어볼게!

arr = [1, 4, 3, 6]

위와 같은 배열이 있을 때, 3을 찾는 알고리즘을 구상한다고 해보자.

그럼 반복문을 통해 배열을 전체 탐색해보면 되겠지?

이렇게되면 3의 위치에따라 시간복잡도가 달라질거야...

위와 같은 경우때문에 세가지 경우로 시간복잡도를 나눠.

Big-Ω : 최선의 경우 한번에 찾음

Big-O : 최악의 경우 배열의 길이만큼 걸림

Big-Θ : 평균의 경우 배열의 길이 중간만큼 걸림

Big-O

보통 Big-O를 사용해. 위와 같은 경우에는 Big-O가 배열의 길이인 4가 되겠지?

즉 O(n) = n 이 되는 경우야.

O(n)같은 경우는 입력이 많아질수록 계산량이 많아져. 이를 선형시간 알고리즘이라고 해.

O(1)은 상수시간 알고리즘이라고 해. 입력의 크기와 상관없이 상수의 시간이 걸린다는 뜻이야.

입력의 크기와 상관없이 100번의 시간이 걸린다고 해도 O(1)으로 표기해!

그 외에도 여러 알고리즘이 있어.

O( 1 ) > O( log(n) ) > O( n ) > O( nlog(n) ) > O( n**2 ) > O( 2**n ) > O( n! )

오른쪽으로 갈수록 성능이 좋지 않아.

만약 n**2 + 2n + 100의 성능을 보이는 알고리즘이 있다면

가장 영향을 많이 미치는 n**2만 남기면 돼. 즉 O(n**2)이야.

3n**2 + 100이라면?

O(3n**2)?

맞아.

하지만 상수는 큰 의미가 없으므로 O(n**2)으로 표기하면 돼.

배열

배열은 값을 접근하고 읽는데에 O(1)만큼의 시간이 걸리므로 접근에는 용이하지만,

데이터를 추가하고 제거하는데에는 내부적으로 필요한 단계가 많이 들기때문에, 성능이 좋지 않아.

또한 미리 공간을 할당하기 때문에 낭비되는 공간이 존재할 수 있다는 단점이 있어!

하지만 일반적인 배열과는 다르게 자바스크립트에서의 배열은 불연속적으로 값을 할당해.

Linked List

일반적인 배열의 단점을 보완하려면 어떻게 하면 좋을까?

바로 저장하려는 데이터들을 메모리 공간에 분산해 할당하고, 이 데이터들을 연결하면 돼.

위 행위는 노드(node)라는 것을 만들어 수행해.

노드는 데이터를 담는 변수, 다음 노드를 가리키는 변수 하나를 갖고있어.

첫 노드의 주소만 알고있다면, 모든 노드에 접근할 수 있어.

이를 Linked list라고 해.

장점으로는 배열처럼 초기 크기를 알아야한다는 단점이 없어!

또한 중간에 데이터를 삽입하려면, 다음을 가리키는 변수만 바꿔주면되기때문에 간단하다는 장점도 있어.

단점으로는 데이터 참조가 O(n)의 성능을 가진다는 거야.

배열 vs Linked List

참조 : 그림으로 쉽게 배우는 자료구조와 알고리즘 (기본편)

• 1주차 회고

  • 칭찬하고 싶은 점 : 기한을 지켰다 😅

  • 아쉬웠던 점 : 권장 커리큘럼을 지키지 못했다.

  • 다음 주에는 권장 커리큘럼을 지켜 수강하는 것이 목표입니다!