#21.05.13 Section5 - Sprint2 (1)

TDL

자료구조

NOTE1

1. 자료구조 = 효율성

   • 자동화
   • 빠른 계산(계산기)
   • 반복 처리, 조건처리
   • 여러개 값 동시 처리
   • 값이 빠르게 변경되는 경우의 처리
   • 특정 변수 처리
   • 특정 값 -> 다양한 형태로 보기

2. 자료구조 - 파이썬 : 리스트와 튜플을 통해 자료구조의 기본인 배열을 구현할 수 있다.

3. 배열(array) : 하나의 변수에 여러개의 인덱스를 묶는 것. 리스트와 튜플

4. 파이썬의 시퀀스 자료형 : 리스트(배열), 튜플(배열), Range(반복), string(문자열)

5. 컴퓨터과학의 자료구조 : 스택, 큐, 리스트(연결리스트 기반), 트리, 그래프

6. 자료구조와 효율성

   • 복잡성, Big O 표기법(알고리즘 성능 분류)
   • 소스코드 효율성 & 프로그램의 효율성

7. Big O 표기법 (notation)

   • 알고리즘 실행 효율성을 측정(데이터 입력값 크기에 따라 알고리즘 실행 속도를 설명하는 방법.)
   • 해당 코드가 얼마나 수행되었는지(ex.연산을 반복한 횟수)에 따라 효율성을 확인함.
   • 알고리즘 계산 복잡도 종류
     (하드웨어 성능 증가로 공간 복잡도보다 소프트웨어 성능인 시간 복잡도가 더 중요하게됨)
     - 시간 복잡도 : 걸린 실행시간
     - 공간 복잡도 : 필요한 메모리 저장 공간
   • 빅오표기법(O(n))만으로 성능을 예측할 수는 없다.
     예를 들어, 실제 실행시간이 30n+1000와 같이 나왔더라도 빅오표기법으로는 O(n)으로 표현되기 때문에 실제 성능과 같을 수는 없다.

8. Big O run times 비교

입력값(n) = 10
log(10) = 1
10 = 10
10log(10)=10
102=100
210=1024
10!=3628800