O (1), O (n log n) 및 O (log n) 복잡도를 갖는 알고리즘의 예

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) : 이진 검색

이것은 숙제 / 면접 질문처럼 들리기 때문에 직감 응답이 될 것입니다. 좀 더 구체적인 것을 찾고 있다면 대중은 일반적으로 인기있는 애플리케이션의 기본 구현 (물론 오픈 소스 절약)을 알지 못하며 일반적으로 개념이 "애플리케이션"에 적용되지 않기 때문에 조금 더 어렵습니다.

---

소프트웨어 애플리케이션의 복잡성은 측정되지 않으며 big-O 표기법으로 작성되지 않습니다. 알고리즘 복잡성을 측정하고 동일한 도메인의 알고리즘을 비교하는 데만 유용합니다. 대부분의 경우 O (n)이라고하면 "O (n) 비교 "또는 "O (n) 산술 연산"을 의미합니다. 즉, 알고리즘 또는 응용 프로그램 쌍을 비교할 수 없습니다.

---

O (1) : 체스에서 최고의 다음 행마를 찾는다 (또는 그 문제를 위해 이동). 게임 상태의 수가 한정되어 있으므로 O (1)뿐입니다. :-)

---

O (1)-이중 연결 목록에서 요소 삭제. 예 :

typedef struct _node {
    struct _node *next;
    struct _node *prev;
    int data;
} node;


void delete(node **head, node *to_delete)
{
    .
    .
    .
}

---

목록에 다음 알고리즘을 추가 할 수 있습니다.

O(1)-숫자가 짝수인지 홀수인지 결정; HashMap 작업

O(logN) -x ^ N 계산,

O(N Log N) -가장 오래 증가하는 하위 시퀀스

---

O (n log n) is famously the upper bound on how fast you can sort an arbitrary set (assuming a standard and not highly parallel computing model).

---

0(logn)-Binary search, peak element in an array(there can be more than one peak) 0(1)-in python calculating the length of a list or a string. The len() function takes 0(1) time. Accessing an element in an array takes 0(1) time. Push operation in a stack takes 0(1) time. 0(nlogn)-Merge sort. sorting in python takes nlogn time. so when you use listname.sort() it takes nlogn time.

Note-Searching in a hash table sometimes takes more than constant time because of collisions.

---

O(2^N)

O(2^N) denotes an algorithm whose growth doubles with each additon to the input data set. The growth curve of an O(2^N) function is exponential - starting off very shallow, then rising meteorically. An example of an O(2^N) function is the recursive calculation of Fibonacci numbers:

int Fibonacci (int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}

참고URL : https://stackoverflow.com/questions/1592649/examples-of-algorithms-which-has-o1-on-log-n-and-olog-n-complexities