[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)
{
    .
    .
    .
}