목록ComputerScience (34)
Nagie's DevStory
O(n²)은 입력 크기 n에 대해 제곱 비례하는 시간 복잡도를 가지는 알고리즘을 나타낸다. 즉, 입력 크기가 증가함에 따라 실행 시간이 제곱으로 증가하며 이는 일반적으로 중첩된 반복문이 있는 경우 발생한다. O(n²)의 시간 복잡도를 갖는 알고리즘의 예시로는 다음과 같은 이중 반복문이 있다. void bubble_sort(int data[], int n) { for (int i = (n - 1); i > 0; i--) { //이중 for 반복문 내부 문장이 ½n(n - 1)번 실행 : O(n) for (int j = 0; j data[j + 1]) { swap(data[j], data[j + 1]); } } } }
O(n)은 선형 시간 복잡도를 나타내며, 입력 크기에 선형으로 비례하여 실행 시간이 증가하는 알고리즘을 의미한다. 즉, 입력 크기가 n일 때, 실행 시간은 n에 정비례한다. 예시 1 int summation(int data[], int n) { int sum = 0; for (int i = 0; i < n; i++) { //for 반복문 내부 문장이 n번 실행 : O(n) sum = sum + data[i]; } return sum; } 예시 2 int variance(int data[], int n) { int sum = 0; for (int i = 0; i < n; i++) { //for 반복문 1 sum = sum + data[i]; } double mean = static_cast(sum) / n..
O(1)은 상수 시간 복잡도를 나타내며, 입력 크기에 상관없이 실행 시간이 일정한 알고리즘을 의미한다. 아래는 O(1)의 예시 코드이며 이 코드는 배열의 요소를 반환하는 간단한 함수로서 입력의 크기가 어떻든 상관없이 항상 상수 시간에 실행된다. int middle(int data[], int b) { return data[n / 2]; //n 값에 관계없이 1회 연산이 실행 : O(1) }
알고리즘이 어떻게 실행 시간과 관련이 있는지를 나타내는 개념이며, 구체적으로는, 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 나타내는 것이다. 시간 복잡도는 주로 빅 오 표기법(Big-O Notation)을 사용해 표현되며, 알고리즘의 성능을 상한선으로 나타낸다. 시간 복잡도를 평가할 때는 최악의 경우를 고려하며 최선의 경우나 평균적인 경우에 대한 시간 복잡도도 중요하지만, 최악의 경우를 고려하는 이유는 알고리즘이 어떤 입력에 대해서도 항상 특정 실행 시간을 보장하기 위함이다. 아래는 대표적인 빅 오 표기법의 예시이다. 빅 오 표기법 이름 설명 O(1) 상수 함수 (Constant Function) 입력의 크기와 무관하게 일정한 시간 소요 O(log n) 로그 함수 (Logari..
알고리즘이란 컴퓨터로 문제를 해결하기 위한 일련의 단계나 규칙들의 집합으로, 입력된 데이터를 특정 출력으로 변환하는 과정을 정의하는 계산적인 절차를 의미한다. 주로 컴퓨터 과학, 수학, 공학 등 다양한 분야에서 사용되며, 효율적인 문제 해결과 데이터 처리를 위해 중요한 역할을 한다. 다음은 컴퓨터 알고리즘의 핵심 개념과 특징을 간략하게 설명한 표이다. 특징 설명 입력과 출력 하나 이상의 입력을 받아들이고, 이를 처리하여 원하는 결과물인 출력을 생성한다. 유한성 유한한 단계로 실행되어야 한다. 어떠한 경우에도 무한 루프에 빠지지 않아야 한다. 정확성 정확한 결과를 산출해야 한다. 주어진 입력에 대해 올바른 출력을 생성하는 것이 중요하다. 효율성 문제를 효과적으로 해결하는 데 걸리는 시간과 자원을 말하며, ..