[자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자료구조 개론
자료구조와 알고리즘을 이해해서 프로그램에 알맞은 코드를 짜 보는 것이 목표..!
공부하다보면 언젠가 깨닫게 되겠지 !! 저는 자바스크립트로 공부합니닷!
자료구조 개론(자료구조란)
1. 자료구조란
자료구조란 다수의 Data를 담기 위한 구조이다.
1-1. 자료구조의 필요성
시스템 기능에 따른 절한 자료구조를 선택하는 것이 최종 성능을 크게 좌우한다.
따라서 자료구조와 알고리즘을 제대로 이해하지 못하면 불필요하게 메모리와 계산(연산)을 낭비 할 것이다.
2. 자료구조의 종류
2-1. 선형 자료구조
하나의 데이터에 다른 데이터가 하나 존재하는 자료구조. 즉, 데이터가 일렬로, 연속적으로 연결되어 있는 형태.
- 예) 배열, 연결리스트, 스택, 큐, 덱
2-2. 비선형 자료구조
하나의 데이터 뒤에 다른 데이터가 여러개 올 수 있는 자료구조. 데이터가 일직선상으로 연결되어 있지 않아도 상관 없다.
- 예) 트리, 그래프
3. 자료구조 성능 비교 (Big-O)
자료구조를 구현하기 위해서는 알고리즘이 필요하고, 알고리즘 문제를 풀기 위해 자료구조를 사용하기 때문에 각 시스템이나 기능을 구현 할 때 어떤 자료구조와 알고리즘이 좋은지 혹은 적절히 사용되고 있는지에 대한 기준도 명확히 알아야 한다.
- 시간복잡도(Time complexity)
- 알고리즘이 문제를 해결하기 위해 사용되는 시간(연산) 횟수를 나타낸다.
- 공간복잡도(Space complexity)
- 알고리즘이 문제를 해결하기 위해 사용하는 메모리의양(공간)을 측정한다.
⭐️ 보통 공간(메모리의양)을 많이 사용하는 대신 시간(연산 횟수)를 단축하는 방법이 많이 쓰인다.
3-1. Big-O 표기법(시간복잡도 표기법: 빅오표기법)
이러한 시간복잡도를 표기할 수 있는 표기법이 Big-O 표기법이다.
빅오표기법은
- 특정 알고리즘이 얼마나 효율적인지 수치적으로 표현이 가능하다.
- 가장 빠르게 증가하는 항만을 고려하는 표기법이다. (최고차항만 표기)
- 가장 큰 항에 붙어있는 계수는 제거한다. (상수항과 계수항은 제거)
표기 예시
O(3n²+n) ⇒ O(3n²) ⇒ O(n²)
4. 빅오 표기법의 종류
4-1. O(1) (상수시간) - 가장 빠름
입력의 크기와 상관 없이 항상 같은 시간이 걸리는 알고리즘으로 데이터 증가에 영향을 받지 않는 알고리즘이다.
4-2. O(logN) (로그시간)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 짧아지는 알고리즘
입력값 n이 주어졌을때, 문제를 해결하는데 필요한 단계들이 연산마다 줄어드는 알고리즘이다.
4-3. O(N) (선형시간)
입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 알고리즘
4-4. O(NlogN) (선형로그시간)
입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 늘어나는 알고리즘
4-5. O(N^2) (제곱시간)
입력 데이터의 크기의 제곱만큼 처리시간이 걸리는 알고리즘 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.
4-6. O(2^N) (지수시간)
입력 데이터의 크기에 따라 걸리는 시간은 2의 n 제곱만큼 비례하는 알고리즘
4-8. O(N!) (팩토리얼 시간) - 가장 느림
입력 데이터의 원소들로 만들 수 있는 모든 순열의 모든 수를 도출할 때
'CS > 자료구조 & 알고리즘' 카테고리의 다른 글
| [자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 스택(Stack) (0) | 2023.07.04 |
|---|---|
| [자료구조] 비전공자 자바스크립트 자료구조와 알고리즘 이해하기 - 자바스크립트 자료구조(배열과 리스트) (0) | 2023.06.30 |
