Algorithm

🚀 시간복잡도 분석과 성능 비교 💡 시간복잡도란? 시간복잡도(Time Complexity)는 알고리즘이 입력 크기에 따라 실행 시간이 어떻게 증가하는지를 나타내는 지표입니다. O(1): 상수 시간 - 입력 크기와 무관하게 일정한 시간 O(n): 선형 시간 - 입력 크기에 비례하여 시간 증가 O(n²): 제곱 시간 - 입력 크기의 제곱에 비례하여 시간 증가 O(log n): 로그 시간 - 입력 크기가 증가해도 천천히 시간 증가 📊 성능 비교 차트 ..

빅오에 대한 공식 소개 Big O Definition We say that an algorithm is O(f(n)) if the number of simple operations the computer has to do is eventually less than a constant times f(n), as n increases.²²² Big O Notation is a way to formalize fuzzy counting. It Allows us to talk formally about how the runtime of an algorithm grows as the inputs grow. 빅오는 대략적으로 숫자를 세는 것에 붙인 공식적인 표현이다. 입력된 내용이 늘어날 수록 알고리즘의 실행 시간이..

연산 갯수 세기 코드가 실행될 때 걸리는 정확한 시간을 초로 측정하는 것보다는 컴퓨터가 처리하는 연산 갯수를 세면된다. 단순하게 만들어서 이 알고리즘은 실핼될때 연산은 5번해야하고 어떤 알고리즘은 7번해야 한다면, 컴퓨터의 사양과는 상관없이 시간은 항상 연산의 갯수에 달려 있을 것이다. 연산이 빠른편이었던 두번째 코드의 연산 갯수를 살펴보자. 곱하기, 더하기, 나누기 총 3개의 연산이 있는 것을 알 수 있다. n이 2든 1억이든 계산은 딱 3번만 이루어 진다. 이것을 첫번째 코드를 살펴보자. for문안에 위치한 '+'는 루프문안에 있기 때문에 n이 5라면 연산이 5번 이루어지게 된다. n이 20이라면 20번 연산이 이루어진다. n이 1억이라면 1억의 연산이 생기게 된다. 여기에 '='도 연산자이기 때문에..

빅오 (Big O)란 무엇인가? 어떤 문제를 해결하기 위한 방법이 2가지 이상이 있다고 생각해보자. 하나는 for문을 사용하고 다른 방법은 문자열을 이용해서 해결한다고 가정해보자. 어떤 것이 더 좋은 코드인지 어떻게 알 수 있을까? 그때 Big O가 필요하다. 즉, 빅오(Big O)란 여러가지 코드를 서로 비교하고 성능을 평가하는 방법이다. 코드 시간 재기를 통해 그 사례를 알아보자! 코드 시간 재기 1에서부터 특정한 N값과 사이에 있는 모든 숫자들을 더하는 Function을 작성한다고 가정해보자. (Suppose we want to write a function that calculates the sum of all numbers from 1 up to (and including) some number..