반응형
SMALL
MenOfPassion(A[], n) {
sum <- 0;
for i <- 1 to n - 1
for j <- i + 1 to n
sum <- sum + A[i] × A[j]; # 코드1
return sum;
}
ex ) i = 7
i 는 1~7-1 (6까지)
j 는 1+1~7
1 2 3 4 5 6 7
2 3 4 5 6 7
3 4 5 6 7
4 5 6 7
5 6 7
6 7
2 3 4 5 6 7 -> 6
3 4 5 6 7 -> 5
4 5 6 7 -> 4
5 6 7 -> 3
6 7 -> 2
7 -> 1
즉 7 입력 시 7-1의 합이 나옴
6+5+4+3+2+1 = 21
7(7-1)/2 = 21
즉 n(n-1)/2
import java.util.*;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Long a = sc.nextLong();
System.out.println(a*(a-1)/2);
System.out.println("2");
}
}
시간복잡도 공부해보기
- Big-O(빅-오) ⇒ 상한 점근
- Big-Ω(빅-오메가) ⇒ 하한 점근
- Big-θ(빅-세타) ⇒ 그 둘의 평균
- Big-O 표기법의 종류
- O(1) → 일정한 복잡도, 입력값 크기와 관계없이 즉시 출력값을 뽑아낼 수 있는 것(가장빠름)
- O(n) → 선형 복잡도, 입력값 증가에 따라 시간 또한 같은 비율로 증가, for
- O(log n) → 로그 복잡도, 탐색기법, O(1) 다음으로 빠름, BST의 값 탐색 등
- O(n2) → 2차 복잡도, 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가 ,2중for , 3중 for → O(n3)
- O(2n) → 기하급수적 복잡도, 재귀로 구현하는 피보나치 수열 등
반응형
LIST
'JAVA > JAVA baekjoon' 카테고리의 다른 글
2231번 블랙잭 (0) | 2023.09.01 |
---|---|
24267번 알고리즘 수업0(n3) (0) | 2023.09.01 |
등차수열 (0) | 2023.08.31 |
시간복잡도 (0) | 2023.08.31 |
11653번 소인수분해 (0) | 2023.08.30 |