[Data Structure] Intro - DAY 6

💡 Intro

나는 전공자다! 라고 말하기 부끄러운 전공자다..ㅎ
왜 학교 다닐 때 열심히 안해서 지금 이 고생을 하는지 모르겠지만... 그 땐 진짜 너무너무너무 노잼이었고 당연히 이해도 안 됐다ㅎㅋㅎㅋ
아무튼 다시 개발자가 되고싶어졌으니까 지금부터라도 CS 지식부터 쌓아야된다..!라는 마인드로 자료구조 공부를 주에 한 개념씩 뿌셔보려고 한다!

말도 안되지만 A+ 이었다.. 진짜 지금은 하나도 모른다ㅎㅋㅎㅋ... 그냥 머리에 때려박았을 지도..?

✅ 자료구조 (Data Structure)

효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합!

🧐 그래서 왜 알아야 되는데 ?
어떠한 비지니스 로직을 처리할 때 그 로직에 가장 효과적인 자료구조를 찾아서 쓰는 것이 매우매우 중요하기 때문!

✅ 시간복잡도 (Time Complexity)

입력크기에 대해 어떤 알고리즘이 실행되는데 걸리는 시간

🧐 그러면 시간을 요이땅! 해서 재야하는거야 ?

console.time("test")
let sum=0;
for(let i =0; i<100000; i++){
  sum+=i;
}
console.timeEnd("test")
// test: 1.575ms

이렇게??
근데 이렇게 시간을 재는건 PC 사양이라던가 뭐 여러가지 이유로 달라질 수 있잖아?

그래서!
시간복잡도를 설명할 때는 주어진 입력크기를 기반으로 어떤 알고리즘이, 주요 로직이 몇번 반복됐는지를 중점으로 측정한다!

코드 예제

for(int i=0; i<10; i++){ //---(3)
	for(int j=0; j<n; j++){ //---(2)
		for(int k=0; k<n; k++){ //---(1)
        	if(true) cout<< k << '\n'; 
		}
	}
}

for(int i=0; i<n; i++){ //---(4)
	if(true) cout<< i << '\n';
}

이런 코드에서는
(1) n번 반복
(2) n번 반복
(3) 10번 반복
(4) n번 반복

즉 $10n^2+n$의 시간복잡도를 가지게 된다!

✅ 빅오표기법 (Big-O notation)

복잡도에 가장 영향을 많이 끼치는 항의 상수인자를 빼고 나머지 항을 없애서 복잡도를 나타내는 표기법

🧐 영향을 많이 끼치는 게 어떤건데 ?
입력 크기의 증가에 따라 증가속도가 더 많이 증가하는 거!

🧐 예를 들어 ?
$10n^2+n$의 시간복잡도에서 입력크기가 1에서 100이 된다고 하면 $n^2$은 1 에서 10000이 되고 $n$은 1에서 100이되니까 $n^2$ 항이 가장 영향을 많이 끼치는 항이 된다!

즉!
🧐 $10n^2+n$의 시간복잡도를 빅오표기법으로 나타내면 ?
$O(n^2)$

📊 Big-O Complexity Chart

👀 상수시간 시간복잡도 $O(1)$

입력크기와 상관없이 일정한 시간복잡도를 가지는 것!
ex) 입출력, 사칙연산, 간단한 if문, 배열의 인덱스 참조

🧐 그래서 시간복잡도는 왜 알아야 되는데 ?
효율적인 코드를 만드는 데 기준이 되기 때문!

🧐 예를 들어 ?
어떤 서비스 로직의 시간복잡도가 $O(n^2)$ ➡️ $O(n)$로 변화했다고 하면 $O(n^2)$ 의 로직을 $O(n)$으로 고쳐 성능을 향상시켰다고 하는 기준이 될 수 있는 것!