✒️ 2024-01-06 16:51 내용 수정

• 내용은 위키피디아 내용을 정리했다.
  • https://ko.wikipedia.org/wiki/시간_복잡도

시간 복잡도

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 나타낸 것

• 컴퓨터 과학에서 알고리즘의 시간 복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화한 것
• 시간 복잡도는 기본적인 연산을 수행하는 데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다.
  • 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.
  • 예로 메소드를 보고 대략적인 시간 복잡도를 계산하면 이 메소드가 크기 n의 입력을 처리하는 알고리즘에 필요한 시간이 어느 정도인지 대략적으로 알 수 있다.

빅-오 표기법( O() )

• 계수와 낮은 차수의 항을 제외시키는 방법이다.
• 시간 복잡도를 점근적으로 묘사한 방법이다.
• ex) 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (5n^3+3n)의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n^3) 이다.

최악의 시간 복잡도

• 알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에 사용하는 알고리즘 시간이다.
• T(n) : 크기 n의 모든 입력에 대해 걸리는 최대의 시간

수행 속도 비교

• https://wikidocs.net/206251
• O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n)

1. 상수 시간

T(n) = O(어떤 상수값) : T(n) = O(1)

• 어떤 알고리즘의 T(n) 값이 입력 크기에 구애 받지 않는 값에 의해서 한정될 때의 최대의 시간
• ex) 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 연산을 수행할 때, 이 요소에 접근하는데 걸리는 시간
• 수행 시간은 문제의 크기에 독립적일 필요가 없으나, 수행 시간의 상한은 문제의 크기에 독립적으로 제한된다.

int index = 5;
int item = list[index];

if( true ) then
	상수 시간동안 수행되는 어떤 연산을 실행
else 
	상수 시간동안 수행되는 어떤 연산을 실행

public class Main {
	public static void main(String[] args){
		// MenOfPassion의 시행 횟수는 1번
		System.out.println(1+"\n"+0);
	}
}

2. 로그 시간

T(n) = O(log n)

• 컴퓨터가 이진수 시스템을 사용하기 때문에 보통 log의 밑은 대부분 2 이다.
• 이진트리에서의 연산이나 이진 탐색에서 찾아볼 수 있다.
• 로그 시간 알고리즘은 인스턴스 당 연산이 각 인스턴스에 대해서 최대한 줄어드는 것이 필요하기 때문에 높은 효율을 갖고 있다고 여긴다.
• ex) 문자열을 절반으로 쪼개고, 쪼갠 것 중 오른쪽 문자열을 또 다시 절반으로 쪼개는 것을 반복할 때

var right = function(str) { // 문자열의 오른쪽 절반을 재귀적으로 출력
	var length = str.length;
	var help = function(index) { // 재귀호출부분 : 오른쪽 절반 출력
		if(index < length) {
			consol.log(str.substring(index, length));
			help(Math.ceil(length+index)/2); // 재귀호출부분 : 오른쪽 절반에 대해 help
		}
	}
	help(0);
}

3. 다항 로그 시간

T(n) = O((log n)^k)

• 어떤 상수 k에 대해 다항 로그시간동안 수행된다.

4. 서브 선형 시간

T(n) = o(n)

• 위에서 정의된 시간 복잡도들을 가진 것을 포함하고, O(n^(1/2))인 Grover 탐색 알고리즘을 포함한다.

5. 선형 시간

T(n) = O(n)

• 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가할 수 있다.
• ex) 리스트에 모든 요소를 더하는 과정은 리스트의 길이에 비례하는 시간을 요구한다.
  • 수행시간이 특히 작은 n의 값에 대해 정확한 선형적인 비례형태로부터 상당한 편차를 가질 수 있기 때문에 다소 부정확하다.

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		// MenOfPassion의 시행 횟수는 입력 시간에 비례한다 (O(n))
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		System.out.println(Integer.parseInt(br.readLine())+"\n"+1);
	}
}

6. 유사 선형 시간

T(n) = O(n log^k n)

• 선형 로그 시간은 k=1인 경우다.
• 유사 선형 시간에서 실행되는 알고리즘
  - in-place 합병 정렬(O(n log^2 n )), 퀵 정렬(O(n log n)), 힙 정렬(O(n log n)), 고속 퓨리에 변환(O(n log n)), Monge 배열 계산(O(n log n))

7. 선형 로그 시간

T(n) = O(n log n)

• 알고리즘은 선형 로그 시간동인 실행되기 때문에, 선형 로그항은 선형항보다 빠르게 증가하지만, 1보다 큰 지수를 가진 n의 다항식보다는 느리다.
• ex) 이진 트리 정렬은 n 크기의 배열의 각 요소를 하나하나 넣어 이진 트리를 만든다.

8. 다항시간

T(n) = O(n^k)

• 입력 크기에 어떤 다항 표현의 상한을 가지고 수행되는 알고리즘

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		// MenOfPassion의 시행 횟수는 입력 크기의 제곱에 비례한다 (O(n^2))
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long tries = (long)Math.pow(Long.parseLong(br.readLine()),2);
		System.out.println(tries+"\n"+2);
	}
}

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		// MenOfPassion의 시행 횟수는 입력 크기의 제곱에 비례한다 (O(n^2))
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long sum = 0;
		for(int i = 1; i < n; i++) { sum += i; }
		System.out.println(sum+"\n"+2);
	}
}

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		// MenOfPassion의 시행 횟수는 입력 크기의 세제곱에 비례한다 (O(n^3))
		// Math.pow(double a, double b)로 인해 실수 표현에서의 오차, 그리고 long형 처리때문에
		// 값이 정확하지 않음
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		System.out.println(n*n*n+"\n"+3);
	}
}

import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		// MenOfPassion의 시행 횟수는 입력 크기의 세제곱에 비례한다 (O(n^3))
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		long n = Long.parseLong(br.readLine());
		long sum = 0;
		for(int i = 1; i <= n - 2; i++) {
			sum += i*((n-2)-(i-1));
		}
		System.out.println(sum+"\n"+3);
	}
}