Stack, Queue는 이전에 공부하고 정리한 것이 있으므로 (요기)
시간복잡도에 관한 내용만 정리하였다!
✅️ 시간복잡도
시간복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.
다른의미로는 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것이다.
왜 실행시간이 아닌 연산수치로 판별할까? 위에도 설명했지만 명령어의 실행시간은 컴퓨터의 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려하는 것이다.
✅️ 시간 복잡도 유형
- 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
- 빅-세타 : 보통일 때의 연산 횟수
- 빅-오 : 최악일 때의 연산 횟수
✅️ Big-O
- 코딩 테스트에서는 모든 케이스를 통과해야 하므로 빅-오 표기법을 기준으로 수행시간을 계산하는 것이 좋다.
✅️ Big-O 표기법의 종류
- O(1) : 일정한 복잡도. 입력값이 증가해도 시간이 늘어나지 않는다.
- 스택의 push,pop, 배열의 인덱스를 찾을 때
- O(n) : 선형 복잡도. 입력값이 증가하면 시간도 같은 비율로 증가한다.
- for문
- O(log n) : 로그 복잡도. O(1) 다음으로 빠른 시간 복잡도를 가진다. 매번 입력값이 절반으로 줄어들 때 로그 복잡도를 가진다고 한다.
- 이진 탐색 트리
- O() : 2차 복잡도. 입력값이 증가하면서 시간이 n^2의 비율로 증가한다.
- 이중 for문
- O() : 기하급수적 복잡도.
- 피보나치 수를 구하는 알고리즘
https://www.freecodecamp.org/news/big-o-cheat-sheet-time-complexity-chart/
✅️ 시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- for문이 1개일 때와 3개일 때 연산 횟수는 N과 3N으로 3배 차이가 나지만 코딩 테스트에서 상수를 무시하기 때문에 시간 복잡도는 O(n)이다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
- 이중 for문이 있을 경우 일반 for문이 10개가 있어도 이중 for문이 시간 복잡도의 기준이 되기 때문에 O()이 된다.
✅️ 시간복잡도를 구하는 요령
각 문제의 시간복잡도 유형을 빨리 파악할 수 있도록 아래 예를 통해 빠르게 알아 볼수 있다.
하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
컬렉션 정렬을 사용하는 경우 : O(n*log(n))
✅️ 이전에 공부한 것
- Stack, Queue
🤓️ 느낀점
스터디 방향성을 얘기하는 저번 시간을 제외하고 처음 모여서 공부했다. 전에 배웠던 스택과 큐이지만 새로운 부분도 더 알 수 있어 좋았고, 시간복잡도도 전에는 얄팍하게 알고있었는데 이번에 개념에 대해 자세히 정리하고 공부할 수 있었어서 좋은 시간이었다고 생각된다. 주말에 있을 토이 프로젝트에 대한 의견도 서로 나누고 이틀 뒤 풀어올 알고리즘 문제를 할당했다. 내가 생각한 스터디 방향이랑 맞는 것 같아 기분이 좋다👍️
