Algorithm & Time Complexity

2025. 4. 15. 11:56·📚 STUDY/📈 알고리즘
목차
  1. 📌 알고리즘이란
  2. 📌 알고리즘과 성능
  3. 📌 시간 복잡도
  4. 📌 시간 복잡도 표기법
  5. 📌 알고리즘 분석

📌 알고리즘이란

문제 해결을 위해 정해진 절차, 방법 or 과정을 나타내는 것. 계산 실행을 위한 단계적 절차

 

특성

  • 정확성
  • 수행성
  • 유한성
  • 효율성

알고리즘 분류

  • 문제 해결 방식에 따른 분류
    • 분할 정복 알고리즘 (Divide-and-Conquer)
    • 그리디 알고리즘 (Greedy)
    • 동적 계획 알고리즘 (Dynamic Programming)
  • 문제에 기반한 분류
    • 정렬 알고리즘
    • 그래프 알고리즘
    • 기하 알고리즘
  • 특정 환경에 따른 분류
    • 병렬 알고리즘 (GPU)
    • 분산 알고리즘 (블록체인)
    • 양자 알고리즘

📌 알고리즘과 성능

  • 시간 (빠르기)
  • 공간 (메모리)

📌 시간 복잡도

  • 코드에서 연산의 횟수를 기반으로 표현한 실행 시간
  • 점근 표기법(Asymtotic notation)을 이용해 나타냄
  • O (Big-O), Ω (Big-Omega), Θ (Big-Theta) 표기법이 있음
    • 일반적으로 O (Big-O) notation을 가장 많이 사용

Big-O notation

O(g(n)) = { f(n) : there exist positive constants c and n₀ such that 0 ≤ f(n) ≤ c·g(n) for all n ≥ n₀ }

f(n) is O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 so that for all n ≥ n₀, we have f(n) ≤ c·g(n). In this case, we will say that f is asymptotically upper-bounded by g.

 

✅ f(n)은 n이 충분히 커지면, g(n)의 상수배보다 크지 않다는 것을 의미

✅ g(n)의 성장을 상한선으로 삼아, f(n)의 성장을 묶는 것이 핵심.

 


📌 시간 복잡도 표기법

O-표기의 정의

    • 모든 n ≥ n₀에 대해서 f(n) ≤ cg(n)이 성립하는 양의 상수 c와 n₀가 존재하면, f(n) = O(g(n))이다.

O-표기의 의미

  • n₀와 같거나 큰 모든 n (즉, n₀ 이후의 모든 n)에 대해서 f(n)이 cg(n)보다 크지 않다는 것

 

✅ g(n)을 f(n)의 상한(Upper Bound)이라고 함.

 

자주 사용하는 Big-O notation

  • O(1) : 상수 시간 
  • O(log n) : 로그 시간 
  • O(n) : 선형 시간 (Linear time)
  • O(nlogn) : 로그 선형 시간
  • O(n²) : 이차 시간 
  • O(n³) : 3차 시간 
  • O(nᵏ) : 다항식 시간, k는 상수
  • O(2ⁿ) : 지수 시간

📌 알고리즘 분석

정렬 문제 : n개의 숫자가 입력으로 주어졌을 때, 이를 기준에 맞게 정렬해 출력하는 문제

 

선택 정렬 알고리즘 (Selection Sort)

  • idx 0 값부터 리스트를 순회하며 가장 작은 값을 찾아 위치를 조정하는 방식
for i in range(0, n-1):
    min_index = i
    for j in range(i+1, n):
        if arr[j] < arr[min_index]:
            min_index = j
    swap(arr[i], arr[min_index])
  • 시간 복잡도 : O(n²)
    • 입력 데이터가 정렬되어있든, 아니든 항상
    • 비교 횟수는 n², 교환 횟수는 n임.
  • 공간 복잡도 : O(1)
    • 추가 메모리 사용 없이, 제자리 정렬
저작자표시 (새창열림)

'📚 STUDY > 📈 알고리즘' 카테고리의 다른 글

Merge sort  (0) 2025.05.07
Divide-and-Conquer Algorithm  (0) 2025.04.15
[C++] ios::sync_with_stdio(0); cin.tie(0);  (1) 2025.03.05
[프언] C에서 C++로 갈아타기  (2) 2025.03.05
Diamond-Square Algorithm  (1) 2025.02.21
  1. 📌 알고리즘이란
  2. 📌 알고리즘과 성능
  3. 📌 시간 복잡도
  4. 📌 시간 복잡도 표기법
  5. 📌 알고리즘 분석
'📚 STUDY/📈 알고리즘' 카테고리의 다른 글
  • Merge sort
  • Divide-and-Conquer Algorithm
  • [C++] ios::sync_with_stdio(0); cin.tie(0);
  • [프언] C에서 C++로 갈아타기
엄지잉
엄지잉
공부하는거 올림
  • 엄지잉
    엄지잉의 이것저것
    엄지잉
  • 전체
    오늘
    어제
    • 분류 전체보기 (94)
      • 🏫 학교 (2)
        • 👩‍🏫 교직 (1)
        • 🏢 USG (1)
      • 🌱 탐구 (17)
        • 📷 SLAM (7)
        • 💡 연구 (8)
        • 🌐 BOJ (2)
      • 📚 STUDY (47)
        • 🔥 C (32)
        • 📈 알고리즘 (9)
        • 👀 컴퓨터비전 (5)
        • 🔆 UNITY (1)
      • 🏆 자격증 (23)
        • ⚡ 정처기 (17)
        • 🔠 TOEIC (6)
      • 🎈 활동 (4)
        • 🎁 CJ 리모트 인턴십 (2)
        • 😶 기타 (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • Github
  • 공지사항

  • 인기 글

  • 태그

    정보시스템 구축관리
    C언어
    C++
    azurekinect
    토익
    2022년
    2021년
    Azure Kinect
    DB 구축
    Remote Internship
    Unity
    프언 활용
    c기초
    알고리즘
    정보처리기사
    opencv
    mocopi
    식별자
    필기
    Body Tracking
    실기
    Slam
    SW 개발
    RC
    정처기
    SW 설계
    BOJ
    컴퓨터비전
    모션캡처
    C
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
엄지잉
Algorithm & Time Complexity
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.