C# #18 알고리즘의 기본 개념

알고리즘

• 알고리즘은 문제를 해결하기 위한 단계적인 절차나 방법을 뜻함.
• 프로그래밍에서는 주어진 입력을 처리하여 특정한 출력을 만드는 방법을 가져오는데 사용됨.
• 효율적인 알고리즘은 시간, 메모리 등 자원의 효율성을 증가시킴.

 

Big O 표기법

• 알고리즘의 효율성(시간 복잡도와 공간 복잡도)을 나타내는 데 사용되는 표기법.
• 입력에 따른 시간과 공간이 필요로 하는 양을 설명하기 위해 사용됨.
• 빅오 표기법은 큰 영향을 주는 부분을 중심으로 계산이 진행되어 최고 차수 항목만 남기고 상수를 버림.

 

• 빅오 표기법은 다음과 같은 주요 형태를 가지고 있음.
• O(1): 상수 시간 복잡도,입력 크기에 무관하게 항상 일정한 시간이 소요됨.
• O(log n): 로그 시간 복잡도, 입력 크기에 비례하지 않고 빠르게 증가함.
• O(n): 선형 시간 복잡도, 입력 크기에 비례하여 시간이 증가함.
• O(n^2): 다항 시간 복잡도, 입력 크기에 대해 제곱에 비례하여 시간이 증가함.

 

시간 복잡도

• 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도.
• 시간은 시계로 측정하는 시간이 아닌 알고리즘이 실행되는 데 걸리는 기본적인 연산 횟수나 단계를 의미함.
• 예를 들어, 배열의 모든 요소를 순차적으로 확인하는 알고리즘의 시간 복잡도는 O(n)임.

 

공간 복잡도

• 알고리즘이 실행되는 동안 필요한 메모리 공간의 양을 나타내는 척도.
• 시간 복잡도와 공간 복잡도는 반비례 관계를 가지고 있음.
• 예를 들어, 정렬 알고리즘이 입력 데이터에 따른 추가적인 배열을 사용하여 정렬된 결과를 저장한다면, 추가적인 배열이 입력 데이터의 크기에 비례하여 메모리를 차지하기 때문에 알고리즘의 공간 복잡도는 O(n)임.