[algorithm] O (1), O (n log n) 및 O (log n) 복잡도를 갖는 알고리즘의 예
O (1), O (n log n) 및 O (log n) 복잡성을 가진 우리가 매일 사용하는 알고리즘은 무엇입니까?
답변
질문에 주어진 시간 복잡성을 가진 알고리즘 / 문 그룹의 예를 원한다면 여기에 작은 목록이 있습니다.
O(1) 시각
- 배열 인덱스 액세스 (int a = ARR [5];)
- 링크 된 목록에 노드 삽입
- 스택에 푸시 및 팝
- 대기열에서 삽입 및 제거
- Array에 저장된 트리에서 노드의 부모 또는 왼쪽 / 오른쪽 자식 찾기
- 이중 연결 목록에서 다음 / 이전 요소로 이동
O(n) 시각
요컨대, 모든 Brute Force 알고리즘 또는 선형성을 요구하는 Noob 알고리즘은 O (n) 시간 복잡성을 기반으로합니다.
- 배열 탐색
- 연결 목록 탐색
- 선형 검색
- 연결 목록에서 특정 요소 삭제 (정렬되지 않음)
- 두 문자열 비교
- 회문 확인
- 계산 / 버킷 정렬 및 여기에서도 이러한 예를 수백만 개 더 찾을 수 있습니다 ….
O(log n) 시각
- 이진 검색
- 이진 검색 트리에서 가장 큰 / 가장 작은 숫자 찾기
- 선형 기능을 기반으로하는 특정 분할 및 정복 알고리즘
- 피보나치 수 계산-최상의 방법 여기의 기본 전제는 완전한 데이터를 사용하지 않고 매 반복마다 문제 크기를 줄이는 것입니다.
O(n log n) 시각
‘log n’의 인수는 Divide와 Conquer를 고려하여 도입되었습니다. 이러한 알고리즘 중 일부는 가장 최적화 된 알고리즘이며 자주 사용됩니다.
- 병합 정렬
- 힙 정렬
- 빠른 정렬
- O (n ^ 2) 알고리즘 최적화를 기반으로 한 특정 분할 및 정복 알고리즘
O(n^2) 시각
이러한 것들은 O (nlogn) 대응 물이있는 경우 덜 효율적인 알고리즘으로 간주됩니다. 일반적인 응용 프로그램은 여기에서 Brute Force 일 수 있습니다.
- 버블 정렬
- 삽입 정렬
- 선택 정렬
- 간단한 2D 배열 탐색
답변
의 간단한 예는 O(1)수 있습니다 return 23;– 어떤 입력이 고정, 유한 한 시간에 돌아갑니다.
의 전형적인 예 O(N log N)는 좋은 알고리즘 (예 : mergesort)으로 입력 배열을 정렬하는 것입니다.
O(log N)이분법으로 정렬 된 입력 배열에서 값을 찾는 것이 전형적인 예 입니다.
답변
O (1)-대부분의 요리 절차는 O (1)입니다. 즉, 요리 할 사람이 더 많아도 일정한 시간이 걸립니다 (냄비 / 팬의 공간이 부족할 수 있기 때문에 어느 정도 시간이 걸립니다). 요리를 나누어야합니다)
O (logn)-전화 번호부에서 무언가를 찾습니다. 이진 검색을 생각하십시오.
O (n)-책 읽기. 여기서 n은 페이지 수입니다. 책을 읽는 데 걸리는 최소 시간입니다.
O (nlogn)-병합 또는 빠른 정렬을 수행하여 카드를 정렬하지 않는 한 nlogn 인 매일 할 수있는 일을 즉시 생각할 수 없습니다!
답변
몇 가지 일반적인 알고리즘을 제공 할 수 있습니다.
- O (1) : 배열의 요소에 액세스 (예 : int i = a [9])
- O (n log n) : 빠른 또는 병합 정렬 (평균)
- O (log n) : 이진 검색
이것은 숙제 / 면접 질문처럼 들리기 때문에 직감 응답이 될 것입니다. 좀 더 구체적인 것을 찾고 있다면 대중은 일반적으로 인기있는 애플리케이션의 기본 구현 (물론 오픈 소스 절약)을 알지 못하며 일반적으로 개념이 “애플리케이션”에 적용되지 않기 때문에 조금 더 어렵습니다.
답변
O (1) : 체스에서 최고의 다음 행마를 찾는다 (또는 그 문제를 위해 이동). 게임 상태의 수가 한정되어 있으므로 O (1)입니다. 🙂
답변
소프트웨어 애플리케이션의 복잡성은 측정되지 않으며 big-O 표기법으로 작성되지 않습니다. 알고리즘 복잡성을 측정하고 동일한 도메인의 알고리즘을 비교하는 데만 유용합니다. 대부분의 경우 O (n)이라고하면 “O (n) 비교 “또는 “O (n) 산술 연산”이라는 의미입니다. 즉, 알고리즘 또는 응용 프로그램 쌍을 비교할 수 없습니다.
답변
O (1)-이중 연결 목록에서 요소 삭제. 예 :
typedef struct _node {
struct _node *next;
struct _node *prev;
int data;
} node;
void delete(node **head, node *to_delete)
{
.
.
.
}
