아르고스의 물건이다.총계여기 정보는 모두 LeetCode와 Geeksforgeks에서 온 거예요.
요약: Big O Cheat Sheet

수색하다

선형 검색

바이너리 검색

점프 검색

선형 검색

iterate through entire array, to search for intended item

시간 복잡성: O(N)

바이너리 검색

질서정연한 집합에서 특정 값을 검색하다

• Target - value to search for
• Index - current location
• Left, Right - indices from to maintain search space
• Mid - index to apply condition to decide if search left or right

작업 원리

서열의 중간 인덱스를 가져오고 검색 조건을 중간 인덱스에 적용

서로 다른 값에 만족하지 않을 경우 1/2 시퀀스 제거

대상을 찾을 때까지 나머지 절반을 계속 검색합니다

.

복잡성

귀속
시간 복잡성: O(log(n))공간 복잡도: O(log(n))(창고 호출 높이, ~ 두 갈래 나무 높이)
교체했어
시간 복잡성: O(log(n))공간 복잡성: O(1)

public int search(int[] nums, int target) {
    int left = 0;
    int right = nums.length -1;
    int midIdx = ((right - left) / 2 ) + left;

    while (left <= right) {
        if (nums[midIdx] < target) {
            // search in right half 
            left = midIdx +1;
            midIdx = ((right-left) / 2) + left;
        } else if (nums[midIdx] > target) {
            // search in left half
            right = midIdx - 1;
            midIdx = ((right - left) / 2) + left;
        } else {
            // nums[midIdx] == target
            return midIdx;
        }
    }
    return -1;
}

검색 건너뛰기

비교적 적은 항목을 검사한 다음 원소를 뛰어넘거나 뛰어넘어 선형 검색을 합니다. (정렬 그룹에서)

1. Search elements in array by index 0,m,2m etc.
2. find indexes where arr[k*m] < target < arr[(*k+1)m]
3. linear search from k*m till (*k+1)m to find target

건너뛸 블록 크기

시간 복잡도 = (N/m) +m
시간의 복잡도를 최소화하기 위해
1=(N/m)+m
1-m=N/m
m-m2=N
평방미터(북)
따라서 옵션 블록 크기 (m) 는 sqrt (N) 이다

복잡성

공간 복잡성: O(1)시간 복잡성:
최적 블록 크기 m=sqrt (N) 를 가정하면
시간 복잡도 = (N/m) +m
=(N/sqrt(N))+sqrt(N)
=sqrt(N)+sqrt(N)
~ O(sqrt(N))

분류하다

Impt: understand trade offs for each algorithm

초급:n2

기포 정렬(안정)

삽입 정렬(안정)

선택 정렬(안정)

더 복잡: n*log(n), 분할

통합 정렬(안정)

빠른 분류(불안정)

입력한 유형(예를 들어 목록이 반전/거의 정렬됨)에 따라algo는 다른 조작을 실행합니다
4와 5를 선택합니다.합병과 빠른 정렬은 분리해서 치료한다.나누어 다스려 원목을 우세하게 하다.

정렬()

Java 배열.sort () 쌍추축을 사용하여 빠른 정렬
복잡성: O(n log(n))

안정 및 불안정 정렬

Stable: objects with equal keys appear in the same order in sorted output as input.
** if two objects are compared as equal their order is preserved**

출처 SO answer
언제 정렬을 안정적으로 해야 합니까?
같은 원소를 구분할 수 있을 때는 안정적인 정렬이 필요하다.

e.g. multiple criterias for sort. sort by object.A THEN object.B

안정된 방식으로.객체별로 정렬합니다.B. 그리고 반대합니다.대답하다
기수 정렬.
같은 유효한 위치와 값을 공유하는 숫자에 따라 정수를 정렬합니다

1. 거품 정렬

repeatedly swap adjacent elements if they are in the wrong order

처음으로 최대 값을 그룹 끝까지 가져옵니다.두 번째 반복은 두 번째 최대 값을 그룹의 마지막 두 번째 인덱스로 가져옵니다.모든 색인을 오름차순으로 정렬하려면 N번 반복해야 합니다.따라서 n2의 복잡성
시간 복잡도: O (n2)
공간 복잡성: O(1)
마구간: 네.

Input: 4A 5 3 2 4B 1
1st pass: 4A 3 2 4B 1 5
2nd pass:
3 4A 2 4B 1 5
3 2 4A 4B 1 5
3 2 4A 4B 1 5
3 2 4A 1 4B 5
3rd pass:
3 2 1 4A 4B 5
output: 1 2 3 4A 4B 5

2. 정렬 선택

Find minimum element from unsorted part and putting it at the beginning. min element and element at beginning swap places.

우선 정렬되지 않은 부품을 통해 최소값을 얻는다.두 번째는 정렬되지 않은 부품을 통해 두 번째 최소값을 얻을 수 있습니다.정렬되지 않은 섹션의 모든 요소를 정렬하려면 N 프로세스가 필요합니다.
시간 복잡도: O (n2)
공간 복잡성: O(1)
마구간: 아니요.

Input : 4A 5 3 2 4B 1
Output :
1st: 1 5 3 2 4B 4A
2nd: 1 2 5 3 4B 4A
final: 1 2 3 4B 4A 5
swapping of places 4A and 1 made the selection sort unstable

코드 예

void sort(int arr[])
    {
        int n = arr.length;

        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++)
        {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i+1; j < n; j++)
                if (arr[j] < arr[min_idx])
                    min_idx = j;

            // Swap the found minimum element with the first
            // element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

3. 정렬 삽입

best for: small dataset & nearly sorted data
array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in sorted part. (compare one by one with elements in sorted part to find correct position).

class Solution {

  static void insert(int arr[],int i) {
      int num = arr[i];
      int insertionIdx = i;
      for (int j=i-1;j>=0;j--) {
          if (arr[i] < arr[j]) {
              insertionIdx--;
              if (j==0) {
                  break;
              } 
          }else {
              break;
          }   
      }
      for (int x=i;x>insertionIdx;x--) {
          arr[x]=arr[x-1];
      }
      arr[insertionIdx] = num;
  }
  //Function to sort the array using insertion sort algorithm.
  public void insertionSort(int arr[], int n) {
      //code here
      for (int i=1;i<arr.length;i++) {
          if (arr[i] < arr[i-1]) {
              int index = i-1;
              insert(arr,i);
          } 
      }
  }

}

시간 복잡성
모범 사례: O(n)
가장 좋은 경우, 수조는 이미 정렬되었고, 한 번에 통과하여, 정렬되지 않은 부분의 첫 번째 요소가 정렬되지 않은 부분의 마지막 요소보다 큰지 확인합니다.
최악과 평균: O (n2
더 나쁜 상황에서, 수조는 상반된 순서로 정렬된다.삽입하기 전에 알고리즘은 정렬된 전체 세그먼트를 스캔하고 이동합니다.모든 요소에 대해 N번 수행됩니다.그래서
마구간: 네.
입력: 4A 5 3 2 4B 1
출력:
제1관문: 14A5324B
두 번째 관문: 1 2 4A 5 3 4B
세 번째 관문: 1234A 54B
제 4 관문: 1234A 54B
산출:123445

4. 결합 정렬

Divide and Conquer algorithm
Divides the input array into two halves, (until each subarray is only size 2) calls itself for the two halves, and then merges the two sorted halves.

수조는 크기가 1이 될 때까지 반으로 나누어져 있다.크기가 1이 되면, 통합 과정이 시작되고, 완전한 그룹이 통합될 때까지 그룹이 통합됩니다.
시간 복잡도: O(n*log(n))
공간 복잡성: O(n)
마구간: 네.

5. 빠른 정렬

best for: average complexity. Avoid if you cant garuntee a good pivot
Divide and conquer. Pick element as pivot point. Split array into two halves, lower than pivot element and higher than pivot element. Repeat process on subarrays until the halves have lenght of 1. Then combine all the elements back together to 1 array.

시간 복잡성:
최적/평균: O(n*log(n))
최악: O (n2)
샤프트 점이 최대/최소 요소이면 최악입니다.명단은 결코 둘로 나누어지지 않았다.
공간 복잡도: O (대수 (n)
마구간: 아니요.

비교되지 않은 정렬

정렬은 모든 요소를 비교해야 하기 때문에 O (n*log (n) 를 초과하기 어렵다.log(n)를 이기려면 비교 정렬이 필요

takes advantage of the way numbers (specifically integers) are stored in memory.

only work with numbers in a specific range

기수 정렬

계수 정렬

병합 또는 빠른 정렬보다 빠를 수 있음

어떤 정렬 알고리즘을 언제 사용합니까?

삽입
기본적으로 분류된 항목은 드물다.
물거품
선택 항목
병합 정렬

의 가장 좋은 평균치와 최악의 상황은 항상 O(n*log(n)->우리는 항상 평균 분배 목록이다.

데이터 세트가 크면 외부 정렬(공간 복잡도 O(n)))(컴퓨터 장치의 메모리에 적합하지 않은 데이터)
빠른 정렬

최악의 상황을 두려워하면 피해야 한다

는 외의 부분을 고르지 않은 경우에 적용된다.O(log(n)의 공간 복잡도
기수/계수 정렬

정렬 정수

트리 및 그림 - 검색

BFS VS DFS

BFS:

node is in upper level of tree

• shortest path / closest nodes
• more memory (need to keep tarck of current nodes)

DFS:

node is in lower level of tree

• less memory / does path exist?
• can get slow

예컨대

루트와 거리가 멀지 않은 솔루션
BFS

나무가 깊고 솔루션이 적음
BFS(DFS는 긴 시간 소요) 또는

이 나무는 매우 넓다
DFS(BFS에 메모리가 너무 많이 필요함)

솔루션은 흔하지만 나무 속에 깊이 숨겨져 있음
DFS

2개 노드 간 경로
DFS

두 노드 사이에 경로 있음
BFS

제스크트라와 베르만포드 호텔

shortest path between two nodes of weighted graph

짐꾼: 무게를 견딜 수 있다

Djisktra: 효율은 높지만 부권중(탐욕 알고리즘)에 적응하지 못함

Djisktra는 가중치를 마이너스로 수용할 수 없습니다. 왜냐하면 '추가' 가중치가 경로를 영원히 짧게 만들지 않을 것이라고 가정하기 때문입니다.