[ 자료구조 ] 1. 자료구조와 알고리즘

쵸오오오오오잉 입니다

자료구조란?

• 컴퓨터 프로그램을 구현하기위해 연구된것
• 컴퓨터 과학에서 효율적인 접근및 수정이 가능한 자료의 조직
• 컴퓨터에 자료를 효율적으로 저장하는 방식

자료구조 분류

• 단순 자료구조 : 정수 실수 같이 프로그래밍언어에서 제공되는 데이터 타입
  • 정수
  • 실수
  • 문자열
• 선형 자료구조 : 각 자료사이의 앞뒤 관계가 1:1 인 선형적인 구조
  • 리스트
  • 덱
  • 스택
  • 큐
  • 배열
• 비선형 자료구조 : 복잡한 연결관계를 갖는 계층구조 혹은 망구조
  • 트리
  • 그래프

알고리즘이란?

• 어떤 문제를 해결하는 절차
• 프로그램 = 자료구조 + 알고리즘
  • 주어진 상황에따라 적절한 자료구조 를 선택하여 효율적인 알고리즘 을 설계하는것
• 알고리즘의 조건
  1. 입력 : 0개 이상의 입력 존재
  2. 출력 : 1개 이상의 출력 존재
  3. 명백성 : 각 명령어의 의미는 모호하지 않고 명확
  4. 유한성 : 한정된 수 뒤에는 반드시 종료되야함 (무한반복x)
  5. 유효성 : 실행 가능한 연산이여야함

알고리즘 성능 분석

효율적인 알고리즘이란?

• 실행시간이 짧으면서 메모리를 적게 사용하는 알고리즘

공간복잡도 (Space Complexity)

• 알고리즘 실행에 필요한 저장공간 (메모리)
• 시간복잡도에 비해 알고리즘 성능분석에 덜 영향을 끼침
• 다만 환경에따라 공간복잡도가 중요한 상황이 있으며, 메모리를 최소한으로 사용하는 것이 좋음

시간복잡도 (Time Complexity)

• 알고리즘이 실행되는데 걸리는 시간 혹은 연산 횟수
• 객관적인 성능 측정을 위해 연산 횟수로 시간복잡도를 구함
• 컴퓨터에 성능에 따라 다르지만 일반적으로 1초에 1억번 연산 을 기준으로 측정

빅오 표기법

• 입력 크기 n 이 커질때 가장 큰 영향을 주는 항만 남겨서 시간 복잡도를 표현하는 방법
• 상수,낮은 차수,계수는 생략
• 함수의 상한 즉 최악의 경우

$O(3n^2+16n+1) => O(n^2)$

•  
• 가장 차수가 높은 3n^2 에서 계수를 생략하여 O(n^2)

• n^3 n^2 과 같이 차수가 크면 n 의 크기가 조금만 커져도 기하급수적으로 상승그외 표기법
• 빅 오메가 표기법 : 함수의 하한을 표시, 최선의 경우
• 빅 세타 표기법 : 동일 함수로 상한과 하한을 만들수 있는 경우의 수