반응형 기초수학7 시간복잡도(Time complexity)와 공간복잡도(Space complexity) 복잡도(complexity) 알고리즘 성능을 나타내는 척도 시간복잡도(Time Complexity) 어떤 문제를 해결하기 위한 알고리즘의 필요 연산횟수 *빅오(Big-O)표기법 : worst case 빅오메가 : 최선 빅 세타 : 중간 O(1) 상수 시간 O(logN) 로그 시간 O(N) 선형 시간 O(NlogN) 로그 선형 시간 O(N^2) 이차시간 O(2^N) 지수시간 지수시간에서 상수시간으로 갈수록 복잡도가 낮아진다. 공간복잡도(Space Complexity) 어떤 문제를 해결하기 위한 알고리즘의 필요메모리 사용량 빅오표기법을 통해 나타냄. 일반적으로 메모리 사용량 기준은 MB 단위 int[a] = new int [1000]; //4byte가 1000개 //4kb int[][] a = new int.. 2024. 2. 27. 제곱과 로그 제곱 같은 수를 두번 곱한 것. *마이너스 일 때 System.out.println(Math.pow(2,3)); //결과 8.0 System.out.println(Math.pow(2,-3)); //결과 0.125 제곱이 -일 경우 분모로 들어감. System.out.println(Math.pow(-2,-3)); //결과 -0.125 //pow 만들기 static double pow(int a, double b){ double result = 1; boolean isMinus = false; //음수인지 판별. if (b == 0) { return 1; } else if(b < 0) { //b가 음수인 경우 b *= -1; isMinus = true; } for (int i = 0; i < b; i++) .. 2024. 2. 27. 점화식(Recurrence), 재귀함수 점화식 어떤 수열의 일반항을 그 이전의 항들을 이용해 정의한 식 ex) 피보나치 수열 재귀함수 어떤 함수가 자신을 다시 호출해서 작업을 수행하는 방식 반환타입 함수이름 (매개변수) { 종료조건 (없을 시에는 무한루프됨.) ... 함수이름(...) } 3씩 곱해질 때의 n번째 수 구하기 // 1, 3, 9, 27, ... 의 n번째 수 int n = 4; int result = 1; for (int i = 0; i < n; i++) { if (i == 0) { result = 1; } else { result *= 3; } } System.out.println(result); //재귀함수로 구현 static int recursion(int n) { if(n == 1) { return 1; } return .. 2024. 2. 27. 조합 (Combination) 조합 서로 다른 n 개 중 r개를 선택하는 경우의 수 (순서 x, 중복 x) ex) 서로 다른 4명 중 주번 2명 뽑기 int n = 4; int r = 2; int pResult = 1; //순열 구하기 for (int i = n; i >= n- r +1; i--) { pResult *= i; } int rResult = 1; //r!구하기 for (int i = 1; i = n- r +1; i--) { pResult *= i; } int rResult = 1; //r! 구하기 for (int i = 1; i 세자리 자연수 만들기 public class Practice { void combination(int[] arr, boolean[] visited, int depth, int n, int r) {.. 2024. 2. 27. 이전 1 2 다음
