0x00 시간, 공간복잡도
시간복잡도(Time Complexity) ★
입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
빅오표기법(Big-O Notation)
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
일단 5N+3을 보면 누가 봐도 N이 커지면 커질수록 3보다는 5N이 훨씬 크다. 그래서 3을 버리고 5N만 냅두는데, 5N에서 상수 5도 떼고 O(N)으로 나타낸다.
2N+10lgN에서도 N이 커지면 커질수록 10lgN보다는 2N이 훨씬 클테니 2N만 냅두고, 상수 2를 떼서 O(N)으로 나타낸다. N^2+2N+4에서는 N^2이 2N과 4보다 훨씬 크니 O(N^2)이 된다.
NlgN과 N을 비교하면 아무래도 그냥 N보다는 lgN이 곱해진 NlgN이 더 클 것입니다. 그래서 NlgN + 30N + 10은 O(NlgN)이 된다.
마지막으로 값이 그냥 상수일 때는 O(1)이라고 부른다.
공간복잡도(Space Complexity)
- 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
- 512MB = 1.2억개의 int
- int 1개 = 4byte
0x01 정수 자료형
- char (1byte)
- short(2byte)
- int(4byte)
- long long(8byte)
기본 구조
기본 char은 맨 앞이 부호를 결정하는 자리로써 -가 붙는다. 따라서 자료값(2진수) 계산시 계산 결과값이 다르다. 즉, 범위가 달라진다.
Integer Overflow
127에 1을 더하면 어떻게 될까? 컴퓨터는 아무 고민도 하지 않고 시킨대로 계산을 한게된다. 01111111에 1을 더하면 10000000이 된다.
그리고 제일 앞의 칸은-2^7 의 칸이니 10000000은 -128이 됐다. 이렇게 char에서 127+1 = -128이 되는 기적을 같이 목도하게된다. 이게 Integer Overflow의 전부. 컴퓨터는 명령받은 대로 이진수 계산을 했을 뿐인데 다만 그 결과가 옳지 않게 됨.
Integer Overflow를 막는 방법은 아주 쉽다. 각 자료형의 범위에 맞는 값을 가지게끔 연산을 시키면 된다.
0x02 실수 자료형
- float (4 byte) 필드크기: 1, 8, 23
- double (8 byte) 필드크기: 1, 11, 52
2진수에서의 과학적 표기법
Field 는 총 3개이다.
sign필드 : 음수 양수인지 저장
exponent필드: 과학적표기법에서의 지수를 저장
fraction 필드 : 유효숫자 부분을 저장
이렇게 실수를 저장하는 방식을 IEEE-754 format 이라고 부른다.
실수의 성질들 ★
fraction field를 가지고 각 자료형이 어디까지 정확하게 표현할 수 있는지 보면 float은 유효숫자가 6자리[1-10^6 ~ 1+10^6]이고 double은 유효숫자가 15자리[1-10^15 ~ 1+10^15]입니다. 이 말은 곧 float은 상대 오차 10^-16까지 안전하고 double은 10^-15까지 안전하다.
'공부 일지 > 알고리즘' 카테고리의 다른 글
| [바킹독 알고리즘]0x06강 - 큐 (0) | 2023.12.26 |
|---|---|
| [바킹독 알고리즘]0x05강 - 스택 (0) | 2023.12.22 |
| [바킹독 알고리즘]0x04강 - 연결 리스트 (0) | 2023.12.21 |
| [바킹독 알고리즘]0x03강 - 배열 (0) | 2023.12.20 |
| [바킹독 알고리즘]0x02강 - 기초 코드 작성 요령 II (0) | 2023.12.19 |
0x00 시간, 공간복잡도
시간복잡도(Time Complexity) ★
입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계
빅오표기법(Big-O Notation)
주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법
일단 5N+3을 보면 누가 봐도 N이 커지면 커질수록 3보다는 5N이 훨씬 크다. 그래서 3을 버리고 5N만 냅두는데, 5N에서 상수 5도 떼고 O(N)으로 나타낸다.
2N+10lgN에서도 N이 커지면 커질수록 10lgN보다는 2N이 훨씬 클테니 2N만 냅두고, 상수 2를 떼서 O(N)으로 나타낸다. N^2+2N+4에서는 N^2이 2N과 4보다 훨씬 크니 O(N^2)이 된다.
NlgN과 N을 비교하면 아무래도 그냥 N보다는 lgN이 곱해진 NlgN이 더 클 것입니다. 그래서 NlgN + 30N + 10은 O(NlgN)이 된다.
마지막으로 값이 그냥 상수일 때는 O(1)이라고 부른다.
공간복잡도(Space Complexity)
- 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계
- 512MB = 1.2억개의 int
- int 1개 = 4byte
0x01 정수 자료형
- char (1byte)
- short(2byte)
- int(4byte)
- long long(8byte)
기본 구조
기본 char은 맨 앞이 부호를 결정하는 자리로써 -가 붙는다. 따라서 자료값(2진수) 계산시 계산 결과값이 다르다. 즉, 범위가 달라진다.
Integer Overflow
127에 1을 더하면 어떻게 될까? 컴퓨터는 아무 고민도 하지 않고 시킨대로 계산을 한게된다. 01111111에 1을 더하면 10000000이 된다.
그리고 제일 앞의 칸은-2^7 의 칸이니 10000000은 -128이 됐다. 이렇게 char에서 127+1 = -128이 되는 기적을 같이 목도하게된다. 이게 Integer Overflow의 전부. 컴퓨터는 명령받은 대로 이진수 계산을 했을 뿐인데 다만 그 결과가 옳지 않게 됨.
Integer Overflow를 막는 방법은 아주 쉽다. 각 자료형의 범위에 맞는 값을 가지게끔 연산을 시키면 된다.
0x02 실수 자료형
- float (4 byte) 필드크기: 1, 8, 23
- double (8 byte) 필드크기: 1, 11, 52
2진수에서의 과학적 표기법
Field 는 총 3개이다.
sign필드 : 음수 양수인지 저장
exponent필드: 과학적표기법에서의 지수를 저장
fraction 필드 : 유효숫자 부분을 저장
이렇게 실수를 저장하는 방식을 IEEE-754 format 이라고 부른다.
실수의 성질들 ★
fraction field를 가지고 각 자료형이 어디까지 정확하게 표현할 수 있는지 보면 float은 유효숫자가 6자리[1-10^6 ~ 1+10^6]이고 double은 유효숫자가 15자리[1-10^15 ~ 1+10^15]입니다. 이 말은 곧 float은 상대 오차 10^-16까지 안전하고 double은 10^-15까지 안전하다.
'공부 일지 > 알고리즘' 카테고리의 다른 글
| [바킹독 알고리즘]0x06강 - 큐 (0) | 2023.12.26 |
|---|---|
| [바킹독 알고리즘]0x05강 - 스택 (0) | 2023.12.22 |
| [바킹독 알고리즘]0x04강 - 연결 리스트 (0) | 2023.12.21 |
| [바킹독 알고리즘]0x03강 - 배열 (0) | 2023.12.20 |
| [바킹독 알고리즘]0x02강 - 기초 코드 작성 요령 II (0) | 2023.12.19 |
