나만의 총결산 (Leet 코드 탐색 카드에서 온 것)

분석하다.

점진적

측정은 기계의 특정 상수에 의존하지 않는 기능 효율

Guess run time of function in relation to the input size

최악

일반적인 병례.

모든 상황이 고르게 분포된다고 가정

기대치 계산
선형 검색.평균 복잡도 ~O(n/2)~O(n)Full Explanation

입력이 고르게 분포된다고 가정

평균 사례 복잡도 = 비교한 총수/입력수

인덱스 0, 인덱스 1, 인덱스 2...에서 찾은 요소,인덱스 n

평균 복잡성:
= 비교한 횟수/n
= 1 + 2 + 3 + ... + 해당 없음
=(n*(n+1)/2)/n
=(n+1)/2
~O(n/2)
~O(n)

메모

θ(Θ) 기호-->상한과 하한.(최적 및 최악)

큰 O 기호-->상한선(최악)

오메가(Ω) 기호-->하한선(최적상황)

순환하다

O(1)
회로 없음

O(n)
순환, 변수는 상량에 따라 점차 증가한다

for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
}

O(노스캐롤라이나)
네스트된 주기.c는 네스트된 레이어입니다.

for (int i = n; i > 0; i -= c) {
       for (int j = i+1; j <=n; j += c) {
          // some O(1) expressions
}

O(대수 (n)
순환 변수를 상수로 나누다.

for (int i = n; i > 0; i /= c) {
       // some O(1) expressions
}

O(대수(n))
순환 변수는 지수 형식으로 상수를 감소/증가시킨다.

for (int i = 2; i <=n; i = pow(i, c)) { 
       // some O(1) expressions
}

**O(22)

입력 데이터를 한 번 늘릴 때마다 두 배로 증가한다
일반적으로 N-1SO answer의 두 개의 비교적 작은 하위 문제를 구해내어 귀속 알고리즘을 실현한다.

O(n!)
각 요소에 주기 추가하기
SO answer

귀속

귀속수

그리기 귀속 트리

각 등급의 나무에 걸리는 시간을 계산한다.

기본 방법
more details

귀속

function calls itself

무한 순환 피하기: 인민폐는 기본적인 상황이 있다
귀속 함수는 통상적으로 세 부분으로 구성된다

base case - 귀속 생성 답안을 사용하지 않는 장면을 중지한다.

recurrence relation - 기타 모든 상황을 기본 상황으로 간소화하는 규칙 집합.

return-인민폐 반환 물품.보통 두 개의 되돌아오는 문장이 있는데, 하나는 기본적인 상황에 사용되고, 다른 하나는 귀속 관계에 사용된다.

귀속 과정에서 함수는 점점 기본 상황에 가까워질 것이다.기본 상황이 발생했을 때, 함수는 되돌아오고, 이전의 함수 호출은 창고에서 팝업됩니다.반복 관계가 반환되지 않으면 반환 유형이 유효하지 않습니다.

복잡성

이것SO answer은 서로 다른 귀속 함수의 시간 복잡성에 대한 신속한 분석을 제공하였다.

동적 프로그래밍

Basically caching. Break problems down into sub problems.
Solve sub-problems only once and store their solution

자 문제로 나눌 수 있습니까?

귀속해

중복된 하위 문제(예를 들어 피보나치, 하위 문제는 한 번 또 한 번 중복)(캐시->DP 사용)

기록자 문제

기억력/Opti(동적 계획)

optimize recursion problems by storing / caching previous functions. Preventing duplicate calls.

예를 들어 피보나치f(n) = f(n-1) + f(n-2)Fibionacci에서는 여러 개의 반복 호출이 가능합니다.(아래 글 참조, 중복 통화 색상 동일)

복잡성

Article 추가 설명

시간 복잡성

선형

Time Complexity = number of recursion invocations (R) and time complexity of 1 recursion call (O(s))
Time Complexity = R * O(s)

예: 문자열 대칭 이동printReverse(str) = printReverse(str[1...n]) + print(str[0])호출 횟수 = N(문자열 길이)
1 호출의 복잡성 = O(1)따라서 시간 복잡도 = N * O(1) = O(N)

실행 트리

Node = invocation of function. Therefore, number of invocations = number of nodes in tree (N_tree)
Time Complexity = number of nodes in tree (N_tree) * complexity of 1 invocation (O(s))
Time Complexity = N_tree * O(s)

이것도 선형에 사용할 수 있다.선형에서는 모든 노드에 트리 높이의 하위 노드가 있습니다.
귀속 함수의 집행 트리는 n-aray 트리를 형성하는데 그 중에서 n은 귀속 함수가 귀속 관계에 나타난 횟수이다
예: 피보나치f(n) = f(n-1) + f(n-2)귀속 함수는 귀속 관계에서 두 번 나타난다.그래서 집행수는 두 갈래 나무다.

두 갈래 나무의 높이는 N이다.
노드 수 = 높이가 N인 두 갈래 나무의 노드 수
= 20 + 21 + 22 + ... + 2N-1
=2n-1
~O(2N)
따라서 복잡한 시간 소요
= 트리의 노드 * 1회 호출을 실행하는 복잡성
=O(2N)*1
=O(2N)

회고록 이후

앞에서 말한 바와 같이memonization은 중복조를 최소화함으로써 귀속의 복잡성을 최적화시킨다.(즉, 실행 트리의 하위 레벨 수를 감소시킵니다)
예: 피보나치
비망록화 이후 중복 통화는 줄어든다.그래서f(n) = f(n-1) + f(n-2)f(n) = f(n-1) + cache(n-2) f(n-2)의 결과가 지난번 호출f(n-1)에서 계산되기 때문에f(n-1) = f(n-2) + cache(n-3)피보나치 최적화에서 계산f(n-1)은 계산f(n)만 하면 된다.f(n-2) 캐시에 저장됩니다.캐시 (hashmap) 에서 그것을 검색하는 것은 지속적인 작업입니다.
페포나치 = f(n) = f(n-1) + cache(n-2)귀속 함수는 한 번만 호출됩니다.실행 트리의 노드에는 하위 노드가 있습니다.계산에 사용되는 귀속f(n)이 호출f(n-1)됩니다.
시간 복잡성
= 실행 트리의 노드 수 *1 함수 호출의 복잡성
= 실행 트리 높이 *1 함수 호출의 복잡성
= O(N) + O(1)= O(N)

공간 복잡성

귀속되는 공간의 복잡성은 두 가지 주요 구성 부분이 있다.

귀속 관련

비귀속 관련

귀속 관계

일반 함수를 호출할 때 함수를 되돌릴 때 창고의 공간을 방출합니다.그러나 귀속 함수에서 함수(f2)는 다른 함수(f1)를 호출하기 때문에 이 두 함수는 모두 창고에 저장된다.귀속 함수에서 함수는 기본적인 상황에 도달할 때까지 모두 창고에 저장됩니다.

Space complexity = maximum depth of recursion tree

스택 오버플로우

프로그램에 할당된 창고가 최대 제한에 도달하면 프로그램이 붕괴됩니다.

Space complexity of recursion = Height of execution tree.

비귀속 관련

공간과 귀속은 직접적인 관계가 없다.예컨대

스토리지 글로벌 변수

귀속 호출의 중간 결과를 저장합니다.(예를 들어menoization: 함수 호출 결과를 저장할 때hashmap의 공간 복잡도)

후부 귀속

**Javadoes not는 후방 반복/후방 호출 최적화 지원

function is tail recursive if recursive call is last thing executed by function

이것stackoverflow answer은 더 좋은 세부 사항을 제공했다.

// non-tail recursive
function recsum(x) {
    if (x === 1) {
        return x;
    } else {
// non-tail because it does computation + recursive call
        return x + recsum(x - 1);
    }
}
// output
recsum(3)
3 + recsum(2)
3 + (2 + recsum(1))
3 + (2 + 1)
6

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
// tail. only calls recursive function
        return tailrecsum(x - 1, running_total + x);
    }
}
// output
tailrecsum(3,0)
tailrecsum(2,3)
tailrecsum(1,5)
tailrecsum(0,6)
6

꼬리 부분 귀속 호출에서 공간을 절약합니다. 왜냐하면 창고는 모든 함수를 호출할 필요가 없기 때문에 공간을 절약할 수 있습니다.공간 "재활용"

f(x1)로 할당된 공간을 f(x2)로 호출합니다.그리고 f (x2) 는 f (x3) 를 호출합니다.그러나 창고는 f (x2) 에 새로운 공간을 할당할 필요가 없습니다. f (x1) 에 공간을 할당하면 '다시 사용하기' 만 합니다.

** 꼬리 귀속 호출은 비꼬리 귀속 함수로 실행할 수 있습니다. 즉 최적화되지 않은 창고 공간을 사용합니다.이것은 프로그래밍 언어에 달려 있다.Java와 Python은 끝부분 호출 최적화를 지원하지 않습니다.
Javascript???

귀속과 교체

가독성: 너 자신을 되풀이할 필요가 없다.

대창고: 대창고 호출.

두루 다니다.

재귀속 사용 시기

using a tree / convergin something into a tree

역귀로 분치할 수 있다

는 몇 개의 하위 문제로 나뉘는데 이런 하위 문제는 같은 문제의 비교적 작은 실례

이다.

하위 문제의 모든 실례는 성질적으로 같다

각 하위 문제의 해결 방안은 조합하여 수중의 문제를 해결할 수 있다.

분류하다

기포 정렬

삽입 정렬

선택 정렬

통합 정렬

빠른 분류

정렬()

JS: 엔진 덮개 아래에서 JS는 문자열처럼 숫자 목록을 정렬합니다.
[1,2,35,67,7,8]
[1,34,65,7,2,8] --> [1,2,34,65,7,8]