본문 바로가기
728x90
반응형

Coding/Algorithm7

O(n^2) - 이차 시간 팩토리얼, 지수시간에 비해 빠르지만 입력 크기가 커질수록 처리 시간이 급격히 증가하는 알고리즘 범주에 속한다.이 복잡도는 이중 반복문이 포함된 구조에서 자주 나타나며, 작은 입력에선 문제없지만, 큰 입력에서는 비효율적인 성능을 보인다.대표적으로 정렬 알고리즘 중 버블 정렬, 삽입 정렬, 선택 정렬이 이에 해당하며, 브루트포스 방식의 문제 해결에서도 볼 수 있다. 버블 정렬오름차순 기준 배열의 인접한 두 원소를 검사하고 정렬한다. 길이가 n인 배열이 있다.전체 루프 i는 첫 번째부터 마지막 요소 앞 n-1까지 진행한다.내부 루프 j는 인접한 두 요소를 비교하고 더 큰 수인 경우 교환을 진행하여 n - 1 - i까지 진행한다.루프마다 가장 큰 요소가 순서대로 끝에 배치된다. def bubble_sort(ar.. 2025. 7. 12.
O(2^n) - 지수 시간 O(2^n) - 지수 시간O(n!) 시간 복잡도처럼, 지수 시간 복잡도 또한 입력 크기가 조금만 커져도 실행 시간이 급격히 증가하는 대표적인 비효율적인 복잡도이다. 특히, 모든 가능한 경우의 수를 탐색해야 하는 문제에서 자주 나타난다. 부분 집합 생성집합 [1, 2, 3]이 있을 때, 모든 부분 집합의 개수는 2^3 = 8개이다. def subsets(arr): if not arr: return [[]] first = arr[0] rest_subsets = subsets(arr[1:]) # 기존 부분집합들 + first를 포함한 새로운 부분집합들 return rest_subsets + [[first] + subset for subset in rest_subsets].. 2025. 7. 12.
NP - TSP 외판원 문제(TSP)NP는 정답을 빠르게 검증할 수 있는 문제 집합이다. 즉, 어떤 해답이 주어졌을 때, 그것이 맞는지 다항 시간 내에 확인 가능한 문제들을 말한다. NP-complete는 NP 문제 중 가장 어려운 문제들로, NP에 속하면서 모든 NP 문제로부터 다항 시간 내에 환원이 가능한 문제이다. NP-hard는 모든 NP-complete 이상의 난이도를 포함하는 상위 개념이다. 이 집합은 NP를 포함하지 않을 수도 있으며, 검증조차 다항 시간 내에 불가능할 수 있는 문제까지 포함한다. P ⊆ NP NP-complete ⊆ NP NP-complete ⊆ NP-hard TSP는 하나의 경로가 주어졌을 때, 그 경로가 총얼마의 비용을 갖는지 계산하는 데는 O(n)으로 정답을 빠르게 검.. 2025. 7. 11.
P, NP Polynomial time다항 시간다항 시간이란 알고리즘의 실행 시간이 입력 크기 n에 대한 다항식으로 표현되는 경우를 말합니다. 이는 O(n^k ) (k는 양의 상수)와 같은 형태로 나타나는 시간 복잡도를 의미한다. O(n), O(n²), O(n³ + n² + 3), O(log n), O(1) 등은 모두 다항 시간으로 분류되는데 O(log n), O(1)의 경우 엄밀히 말하면 다항식은 아니지만 다항 시간보다 훨씬 효율적이므로 넓은 의미에서 다항 시간 범주에 포함된다. 반면 O(2ⁿ), O(n!)과 같은 복잡도는 다항 n이 커질수록 기하급수적으로 실행시간이 폭증하여 다항 시간이 아니며, 이런 알고리즘은 대개 비실용적으로 간주한다. 어떤 문제에 대해 다항 시간 내에 항상 정답을 찾을 수 있는 알고리즘이 .. 2025. 7. 8.
O(n!) - 팩토리얼 시간 O(n!) - 팩토리얼 시간주어진 배열의 원소들을 가능한 모든 순서로 배열하는 것을 순열 생성의 모든 경우의 수이다. 여기서 순열은 일반적인 순열인 직순열로 일직선상의 배열이다. 이러한 연산에서 n개 원소는 n! 개의 순열이 존재하고, 각 순열을 생성하는 데 걸리는 시간을 포함한 전체 시간 복잡도는 n! * n = O(n!)이다. 순열 생성배열 [1, 2, 3]가 있을 때, 가능한 모든 순열은 다음과 같다. [1, 2, 3], [1, 3, 2],[2, 1, 3], [2, 3, 1],[3, 1, 2], [3, 2, 1] 총 3! = 6가지 경우가 존재한다. 코드로 표현하면 다음과 같다.def permutations(arr): if len(arr) :i i인덱스를 제외한 그 앞의 집합, i+1: 다음.. 2025. 7. 8.
빅-오(Big-O) 표기법 빅-오(Big-O) 표기법빅-오(Big-O) 표기법은 알고리즘이 입력 크기(n)에 따라 수행 시간이나 연산 횟수가 어떻게 증가하는지를 나타내는 수학적 표기법이다. 보통 최악의 경우(Worst Case) 기준으로 시간 복잡도를 분석하며, 다양한 알고리즘의 효율성을 비교하는 데 활용된다. 시간 복잡도는 입력 크기에 따른 실행 시간의 증가율에 따라 여러 등급으로 나뉘며 다음은 효율이 낮은 순서부터 정리한 목록이다.O(n!) - 팩토리얼 시간가능한 모든 순열을 탐색하는 경우외판원 문제(TSP), 순열 생성 등 O(2^n) - 지수 시간모든 부분 조합이나 경우의 수를 탐색할 때부분집합 생성, 피보나치(재귀), DFS/백트래킹 등 O(n^2) - 이차 시간이중 루프를 사용하는 비교 기반 알고리즘버블 정렬, 선택 .. 2025. 7. 8.
728x90
반응형

티스토리툴바