알고리즘 시간 복잡도 정렬 조금

알고리즘

알고리즘은 입력을 받아 원하는 출력을 생성하기 위한 절차입니다.

알고리즘은 주어진 입력에 대해 정확하고 일관된 결과를 제공해야 합니다.

 

Big O 표기법

Big O 표기법은 알고리즘의 효율성을 나타내는 표기법입니다.

• Big O 표기법의 예
  • O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.
  • O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.
  • O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.
  • O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

 

빅오 표기법 계산

1. 상수 버리기 알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.
2. 최고 차수 항목만 남기기 빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.
3. 다항식의 경우 최고 차수 항목만 고려 다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.
4. 연산자 상수 무시 빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

1) 시간 복잡도란?

• 시간 복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도입니다.
• 코드의 실행 시간을 실제 시간(초)으로 측정하는 것이 아니라, 입력 크기에 대한 연산 횟수로 측정합니다.

2) 공간 복잡도란?

• 코드의 메모리 사용량을 실제 메모리 크기(바이트)로 측정하는 것이 아니라, 입력 크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명합니다.
• Big-O 표기법을 사용하여 표시함

 

 

C# Sort

여러 정렬이 있지만   c#의 기본 정렬만 정리해 두었다

1) Sort 메서드

• Sort 메서드는 배열이나 리스트의 요소들을 정렬하는 메서드입니다.
• 정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬 기준을 사용할 수 있습니다.
• Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없습니다.

2) 사용 예제

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers);
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort();
Console.WriteLine(string.Join(", ", names));