728x90
๋ฐ์ํ
์๊ฐ๋ณต์ก๋
์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ ์ํํ๋๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ์ ์ค๋ช ํ๋ ๊ณ์ฐ ๋ณต์ก๋๋ฅผ ๋งํ๋ค.
๋ํ์ ์ธ ๋ฐฉ๋ฒ ๋น ์ค ํ๊ธฐ๋ฒ
Big-O ํ๊ธฐ๋ฒ
์ฑ๋ฅ๋น๊ต
(๋น ๋ฆ) O(1)<O(logN)<O(N)<O(NlogN)<(N^2)O(2^N) (๋๋ฆผ)
๋ฌธ์ ์กฐ๊ฑด์์ ํํธ ์ป๋ ๊ณต์
1์ต๋ฒ ์ฐ์ฐ = 1์ด๋ก ์๊ฐํ๊ธฐ
์๊ฐ ์ ํ์ด 1์ด์ธ ๊ฒฝ์ฐ ์์
N์ ๋ฒ์๋ 2000์ธ ๊ฒฝ์ฐ,
O(N) → 2000๋ฒ ์ฐ์ฐ, 1์ต ์ดํ์ฌ์ ๊ฐ๋ฅ
O(N^2) → 4,000,000๋ฒ ์ฐ์ฐ, 1์ต ์ดํ์ฌ์ ๊ฐ๋ฅ
O(N^3) → 8,000,000,000๋ฒ ์ฐ์ฐ, 1์ต ์ด์์ด๋ฏ๋ก ๋ถ๊ฐ๋ฅ
public class Main {
static int fibonacci(int n) {
if (n < 3) {
return 1;
}
return fibonacci(n - 2) + fibonacci(n - 1);
} // ํผ๋ณด๋์น ๋ฉ์๋
static int factorial(int n) {
if (n < 1) {
return 1;
}
return n * factorial(n - 1);
} // ํฉํ ๋ฆฌ์ผ ๋ฉ์๋
public static void main(String[] args) {
// 1. ์๊ฐ ๋ณต์ก๋
System.out.println("== ์๊ฐ ๋ณต์ก๋ ==");
// O(1)
System.out.println("== O(1) ==");
System.out.println("hello");
// ํ๋ฒ ์ฐ์ฐ (์ถ๋ ฅ ์ฐ์ฐ ํ๋ฒ)
// O(logN)
System.out.println("== O(logN) ==");
for (int i = 1; i < 16; i*=2) {
System.out.println("hello");
}
// 16์ ๋ํ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ ๋, ์์ ์ถ๋ ฅ์ 4๋ฒ๋ง ์ด๋ฃจ์ด์ง.
// O(N)
System.out.println("== O(N) ==");
for (int i = 0; i < 2; i++) {
System.out.println("hello");
}
// N๋ฒ์ ๋ํด์ N๋ฒ๋งํผ ๋ค ์ด๋ฃจ์ด์ง
// O(NlogN)
System.out.println("== O(NlogN) ==");
for (int i = 0; i < 2; i++) {
for (int j = 1; j < 8; j*=2) {
System.out.println("hello");
}
}
// ๋ฐ๊นฅ for๋ฌธ N๋ฒ๋งํผ ์ด๋ฃจ์ด์ง
// ์์ชฝ for๋ฌธ logN๋ฒ ๋งํผ ์ด๋ฃจ์ด์ง
// O(N^2)
System.out.println("== O(N^2) ==");
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
System.out.print("hello ");
}
System.out.println();
}
// N๋ฒ๋งํผ ์ด๋ฃจ์ด์ง๋ for๋ฌธ์ด ์ด์ค์ผ๋ก ์์ ๋
// O(2^N)
System.out.println("== O(2^N) ==");
// ํผ๋ณด๋์น ์ฌ๊ท
// 1, 1, 2, 3, 5, 8, 13, ...
System.out.println(fibonacci(6));
// WORST ์ผ์ด์ค
}
}
https://youtu.be/tTFoClBZutw?si=WTMLY1CIC0tqPZyN
๋ฐ์ํ
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๊ณ ๋ฆฌ์ฆ] DFS์ BFS JAVA (0) | 2024.06.14 |
---|---|
์ด์งํ์(Binary Search) ๊ฐ๋ ์ ๋ฆฌ (1) | 2024.06.11 |
Queue ๊ฐ๋ ์ ๋ฆฌ (0) | 2024.06.11 |
Stack ๊ฐ๋ ์ ๋ฆฌ (0) | 2024.06.11 |
๋ฐฑ์ค 10988 ์๋ฐ ํฐ๋ฆฐ๋๋กฌ์ธ์ง ํ์ธํ๊ธฐ (0) | 2023.12.15 |