자료구조 기초

Grace·2022년 7월 27일
0

Data Structure Visualization
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

Visu Algo (애니메이션을 통한 데이터 구조 및 알고리즘 시각화)
https://visualgo.net/en

자료구조란

자료구조 즉 data structure란 데이터를 어떻게 관리할지에 따라 데이터를 담는 틀입니다.
여기서 관리란 데이터의 검색, 순회, 저장, 삭제, 변경 등의 작업을 의미합니다.
데이터의 형태와 용도에 맞는 구조를 사용하는 것이 중요합니다. 컴퓨터의 자원은 한정적이고 제한된 제약조건 내에서 정확한 결과를 내야하기 떄문입니다.
이렇게 데이터의 형태와 용도에 맞게 자료구조를 사용하려면 자료구조의 특징/장점/한계를 정확하게 이해하고 파악하는 것이 중요합니다.
알고리즘이란 어떤 문제가 주어졌을 떄 문제를 풀기 위한 동작들의 절차입니다. input 값을 통해 output을 내는 일련의 과정이라고 볼 수 있습니다.

빅오 표기법


빅오 표기법이란 여러 자료구조와 알고리즘이 존재할 떄 각각을 비교하기 위해 사용하는 점근표기법 중 하나입니다.
점근 표기법에는 빅오 표기법 이외에도 세타 표기법, 오메가 표기법이 있습니다. 하지만 복잡도를 논할 경우 대부분 빅오를 기준으로 하게 됩니다.
가장 위의 상한 점근이 빅오, 하한 점근이 오메가 표기법, 그리고 상한/하한 점근이 세타 표기법입니다.
점근 표기법은 가장 큰 영향력이 있는 항만 표시하며 상수항은 무시합니다.
우리는 빅오 표기법으로 공간 복잡도시간 복잡도를 표기하게 됩니다.

공간 복잡도

데이터 관리에 필요한 공간을 의미합니다. 데이터 양의 변화에 따른 공간의 변화를 표현할 수 있으며 예상 소요 공간을 측정할 수 있게 도와줍니다.

시간 복잡도

데이터 처리에 소요되는 시간을 의미합니다. 데이터 양의 변화에 따른 소요 시간의 변화를 표현할 수 있으며 예상 처리 시간을 측정합니다. 지연 장애가 발생했을 때 왜 발생했는지를 찾을 수 있는 근거가 됩니다.

시간복잡도

O(1)

입력 데이터의 크기와 상관없이 항상 일정한 시간이 걸리는 알고리즘

  • 배열의 Random Access
  • Hash

O(N)

입력 데이터의 크기에 비례해서 시간이 소요되는 알고리즘

  • for문

O(N²)

입력 데이터의 제곱에 비례해서 시간이 소요되는 알고리즘

  • 이중 for문

O(logN)

  • 이진 탐색(Binary search)

O(NlogN)

  • Merge sort
profile
기술블로그 이전:: https://meercat.tistory.com/

0개의 댓글