⚡ 복잡도, 진수, 실수
📌 복잡도 분석
🔷 알고리즘
- 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법, 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법
효율공간적 효율성: 연산량 대비 얼마나 적은 메모리 공간을 요하는 가시간적 효율성: 연산량 대비 얼마나 적은 시간을 요하는 가효율성을 뒤집어 표현하면복잡도가 되며복잡도가 높을 수록효율성은 저하된다.
🔷 시간적 복잡도 분석
-
하드웨어 환경에 따라 처리시간이 달라진다.
- 부동소수 처리 프로세서 존재유무, 나눗셈 가속기능 유무
- 입출력 장비의 성능, 공유여부
-
소프트웨어 환경에 따라 처리시간이 달라진다
- 프로그램 언어의 종류- 운영체제, 컴파일러의 종류
❗ 이러한 환경적 차이로 인해 분석이 어렵다.
🔷 복잡도의 점근적 표기
- 시간(또는 공간)복잡도는 입력 크기에 대한 함수로 표기하는데, 이 함수는 주로 여러 개의 항을 가지는 다항식이다.
- 이를 단순한 함수로 표현하기 위해
점근적 표기(Asymptotic Notation)을 사용한다. - 입력 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용하는 표기법이다.
1) 빅-오 표기법: 복잡도의 점근적 상한을 나타낸다.
이전에 많이 언급했으니 그냥 넘어가자...
2) 빅 오메가 표기법: 복잡도의 점근적 하한을 의미한다. (최소한 이만한 시간은 걸린다!)
> 💡 빅오 표기법처럼 복잡도 다항식의 최고차항만 계수 없이 취한다.
3) 빅 쎄타 표기법: 빅오 표기와 빅오메가 표기가 같은 경우에 쓰인다.
( f(n)= Θ(n^2) : "f(n)은 n이 증가함에 따라 n^2과 동일한 증가율을 가진다." )
💡 자주 사용하는 O-표기는 다음과 같다.
O(1): 상수 시간
O(logn): 로그(대수) 시간
O(n): 선형 시간
O(nlogn): 로그 선형 시간
O(n^2): 제곱 시간
O(n^3): 세제곱 시간
O(2^n): 지수 시간
🔥 10억 개의 숫자를 정렬하는데 O(n^2)알고리즘은 300여년이 걸리지만 O(nlogn)알고리즘은 5분 만에 정렬한다. 효율성이 중요한 이유...
📌 진수
🔷 진법
-
수를 셀 때, 자릿수가 올라가는 단위를 기준으로 하는 셈법의 총칭
- 일반적으로 10진법
- 시계: 12진법/60진법 , 컴퓨터: 2진법
-
10진수 -> 타 진수로 변환하기
- 원하는 타진법의 수로 나눈 뒤 나머지를 거꾸로 읽는다.
🔷 컴퓨터에서의 음의 정수 표현
-
부호 비트(최상위 비트: 양수 -> 0, 음수 -> 1) -
1의 보수: 부호와 절대값으로 표현된 값을 부호 비트를 제외한 나머지 비트들을 0은 1로, 1은 0으로 변환한다. -
🌟
2의 보수: 1의 보수방법으로 표현된 값의 최하위 비트에 1을 더한다.💡 컴퓨터가 1의 보수가 아닌 2의 보수를 사용하는 이유는 1의 보수는 0이 0과 -0으로 분류되기 때문.
📌 실수
🔷 실수의 표현
- 2진수의 소수점 이하를 10진수로 표기할 수 있다.
❗ 다만 중간중간 구멍이 나기 때문에 이를 유효숫자라고 한다.
- 컴퓨터는 실수를 표현하기 위해 고정 소수점, 부동 소수점 표기법을 사용한다.
⭐ 고정 소수점 방식
| 부호(1 bit) | 정수(15 bit) | 소수(16 bit) |
|---|
⭐ 부동 소수점 방식
- 소수점의 위치를 고정시켜 표현하는 방식
- 소수점의 위치를 왼쪽의 가장 유효한 숫자 다음으로 고정시키고 밑수의 지수승으로 표현
🔷 실수를 저장하기 위한 형식
- 단정도 실수(32비트)
- 배정도 실수(64비트)
💡
가수부: 실수의 유효 자릿수들을 부호화된 고정 소수점으로 표현한것
지수부: 실제 소수점의 위치를 지수 승으로 표현한 것
💡 컴퓨터는 실수를 근사적으로 표현한다. 작은 오차가 계산 과정에서 다른 결과를 가져온다..!
📌 비트 연산
| 연산자 | 연산자의 기능 |
|---|---|
| & | 비트단위로 AND 연산 |
| | | 비트단위로 OR 연산 |
| ^ | 비트단위로 XOR연산 (같으면 0 다르면 1) |
| ~ | 단항 연산자로서 피연산자의 모든 비트를 반전 |
| << | 피연산자의 비트 열을 왼쪽으로 이동 |
| >> | 피연산자의 비트 열을 오른쪽으로 이동 |
public class DailyClass {
public static void main(String[] args) {
// 3 -> 0011
// 5 -> 0101
// &: 두 비트가 모두 1이면 1, 아니면 0
// "해당 비트는 있어요"
System.out.println(3 & 5);
// |: 하나의 비트라도 1이면 1, 둘다 아니면 0
// "해당 비트는 썼어요"
System.out.println(3 | 5);
// ^: XOR, 같으면 0, 다르면 1
System.out.println(3 ^ 5);
// ~: 단항연산자, 모든 비트를 반전 (1의 보수를 취한 것, 1을 더하면 2의 보수가 된다)
System.out.println(~3);
// A << B: A의 비트를 왼쪽으로 B번 이동
// 한번 움직일 때마다 2배씩 커진다
System.out.println(3 << 2);
// A >> B: A의 비트를 오른쪽으로 B번 이동, 소수점은 버려진다
// 한번 움직일 때마다 2배씩 작아진다
// 맨 왼쪽에 추가되는 수는 부호비트에 따라 달라진다
System.out.println(12 >> 2);
}
}
