오늘 배운 내용

- 자료구조

---

Big-O 표기법

• 데이터 연산에 대한 성능을 표현하는 수학적 표기법
• 알고리즘에 대한 성능을 '예측'하는 것이 목적

- 공간 복잡도(요즘은 잘 신경 안씀)

• 프로그램의 실행부터 완료시까지 필요한 저장공간의 양
• 현대의 PC는 하드웨어의 발달로 '비교적' 덜 중요한 개념이 되었다.

- 시간 복잡도

• 프로그램의 실행부터 완료시까지 필요한 과정(시간)의 양
• 알고리즘의 효율성을 결정하는 중요한 요소

- O(1)

• 기능 수행을 위해 한 번의 연산을 수행할 때 사용
• 배열의 크기에 상관없이 단 한번에 접근이 가능
• ex) 배열의 특정 인덱스를 통해서 데이터를 제어하는 상황

- O(n)

• 배열의 크기에 따라 시간이 비례하게 늘어나는 형태
• ex) 1차원 배열을 순회하면서 원하는 데이터를 찾는 상황

- O($n^2$)

• 2차원 배열을 순회하는 구조
• 배열의 순회를 다시 배열의 크기만큼 돌아야 하기 때문에
  배열의 크기가 커질 때마다 점점 수직에 가까워지는 성능을 확인할 수 있다.
• 데이터의 양이 많아지면 많아질수록 시간이 오래 걸린다.

- O(log n)

• 연산이 거듭될수록 남은 예상 연산량이 절반이 될 때 사용된다.