처음에 thedukh에 썼습니다.

In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a given number x is the exponent to which another fixed number, the base b, must be raised, to produce that number x.
-Wikipedia

소개하다.

원래의 댓글을 보고 큰 O 기호에 대한 지식을 업데이트하려면 클릭하세요.
마지막 부분에서, 우리는 코드의 속도와 성능을 알려주는 큰 O 기호를 설명하고 해독했다.우리는 이미 O(1), O(n)와 O(n2) 등 서로 다른 기호의 예를 보고 탐색했다.
큰 O가 운행할 때 또 다른 흔히 볼 수 있는 변체가 있다.다음 그림을 보십시오. 빨간색은 대수 시간의 복잡도를 나타냅니다.잠깐만, 로건.뭐?그래, 자모의 동일한 점을 소개하다가 수학을 잃어버리면 절망하지 마라!😕 😕
처음에는 잘 몰랐을 수도 있지만, 이 글은 그것을 더욱 분명하고 이해하기 쉽게 하기를 바란다.
우리 시작합시다!

이전 문장과 다른 주석

대수

만약 우리가 임의의 b가 있다면 b>0과 b를≠ 1, 우리는 x>0이 있다. 그러면 우리는'x의 대수기 b'는
y=logbx
{y=log_bx}
y=logb​x
이것은
by=x
{b^y=x}
by=x
.
이렇게!만약 네가 처음에 이해하지 못한다면, 대수와 지수는 반함수이다.
**
y=logbx  ⟺  by=x
{y=log_bx\iff b^y=x}
y=logb​x⟺by=x
. 📐 📐
B는 기초이고 x는 매개 변수이며 y는 방정식의 해이다.
상술한 상황 하에서
y=logbx
{y=log_bx}
y=logb​x
대수 형식으로 불리다
by=x
{b^y=x}
by=x
지수 형식이에요.
Log (알파벳 조합) 는 아무런 의미가 없습니다. 대수 연산을 나타내는 함수 이름일 뿐입니다.그래서 만약 우리가 수학 문제의 어느 곳에서든 대수를 보게 된다면 우리는 우리가 대수를 처리하고 있다고 확신할 것이다.
아래에 표시된 매개 변수 b는 조작의 기초를 알려 줍니다. x는 매개 변수입니다.
우리는 단지 어떤 숫자를 b의 지수로 해야만 x를 최종 결과로 얻을 수 있느냐고 묻고 있을 뿐이다.관련 대수와 지수가 무엇인지 기억해야 한다. 간단한 기억 방법은 b의'성장'을 상상하고 x는 항상'등호부터 운행한다'는 것이다. 이렇게 하면 방정식을 맞출 수 있다.🚀
우리는 두 가지 예를 통해 이 문제들을 어떻게 해결하는지 이해합시다.

결과는 어떨까
y=log416{y=log416}
logy=4​16
?

직접 해결 방안을 찾기는 어려울 것이다.해결 방안을 확정하는 가장 좋은 방법은 공식을 지수 형식으로 바꾸는 것이다.들키다
일지
{logu416}
로그 4​16
당장 무섭게 보일 수도 있지만, 그건 알아요.
일지
{logu416}
로그 4​16
및
4?=16
{4^? = 16}
4?=16
갑자기 한결 가벼워진 것 같아!우리가 여기서 찾는 지수는 무엇입니까? 4 곱하기 그 자체로 16을 얻을 수 있습니까?해결책은 당연히
42=16
{4^2 = 16}
42=16
그러면
일지
{logu416}
로그 4​16
네, 맛없어요.

결과는 어떨까
y=log6216{y=log6216}
y=log6​216
?

우리는 다시 대수 형식을 지수 형식으로 바꿀 것이다.
log6216
{log_6216}
로그 6​216
... 과 같다
6?=216
{6^? = 216}
6?=216
어떤 지수가 필요합니까?6 곱하기 그것 자체가 36이다.그래서 그것은 2가 아니다. 우리는 더 큰 지수가 필요하다!우리 다시 해봐야 돼. - 36*6=216!우리는 우리의 지수를 찾았다.그래서
log6216
{log_6216}
로그 6​216
세 살.

결과가 어떻게 될지
y=log1381{y=log{1\over 3}81}
y=log31​81
?

지금
13?=81{\frac{1}{3}^=81}31​?=81
계산해 봅시다.
13−4=34=81\frac{1}{3}{-4}=3^4=8131​−4=34=81
이제 우리는
log1381=−4
{log_{1\over 3}81=-4}
로그 31​​81=−4
. 🤘 🤘
대수에 대한 자세한 내용은 page를 참조하십시오.우리는 이 주제에 대해 충분한 토론을 하여 대수 시간의 복잡성을 정확하게 이해하였지만, 당신은 위의 링크를 보고, 더 많은 연습, 대수의 더 많은 속성과 특수한 대수 유형을 이해할 수 있습니다.

대수 시간 복잡도

다음 그림은 대수의 배율을 보여줍니다.
대수도
효율이 높습니다!우리가 입력의 크기를 늘려도 값은 어느 점에서 수렴되기 시작하기 때문에 고정된 복잡도 이후에 대수 시간의 복잡도가 가장 효과적이다. 이것은 이상하지 않다!
대수 시간의 복잡도는 통상적으로 Divide and Conquer라고 불리는 범례에서 발생한다.분할 치료는 일종의 프로그래밍 모델로 문제를 더욱 작은 하위 문제로 분해한다.모든 하위 문제는 충분히 작아서 해답을 구할 수 있다. 마지막으로 계산이 끝난 후에 하위 문제는 합병된다.분치를 사용하는 일부 표준 알고리즘은 2진법 검색, 빠른 정렬, 통합 정렬이다.
다음 그림은 병합 정렬 알고리즘을 보여 줍니다. 수조 입력은 두 개의 수조로 나뉘어진 다음에 네 개의 수조로 나뉘어집니다. 수조 입력이 충분하게 작아질 때까지 한 항목을 정렬할 수 있습니다.그 다음에 현재 분리된 블록을 한데 조합하여 최종 결과인 정렬수 그룹을 얻는다.
분치합병 정렬도

대수 시간 복잡도 예

O(대수 (n)

나는 단지 분명히 말하고 싶었을 뿐이다.대수 표현법과 관련이 있을 때, 우리는 아래 값을 표시하지 않았다는 것을 알 수 있습니다.우리는 O (logn)만 쓴다.
위의 예에서 우리는 반드시 기수를 써야 한다. 왜냐하면 우리는 대수의 서로 다른 수학 변화를 해결했기 때문이다.데이텀이 지정되지 않은 경우 기본값은 2입니다.그래서 log100은
log10100
{log_{10}100}
로그 10​100
.
이제 재미있는 질문 하나 봅시다.

function binarySearch(array, key) {
  var low = 0;
  var high = array.length - 1;
  var mid;
  var element;
  while (low <= high) {
    mid = Math.floor((low + high)/ 2)
    element = array[mid]
    if (element < key) {
      low = mid + 1;
    } else if (element > key) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1
}

binarySearch([1, 2, 4, 6, 7, 9, 13, 14, 15, 16, 18, 22, 25, 26], 9); // 5

BinarySearch 방법은 두 개의 매개 변수를 받아들인다. 하나의 수조와 몇몇 수조에 있어야 하는 키이다.

초기 변수를 정의합니다.기본적으로 Low는 배열의 첫 번째 요소를 가리키는 0이고 high는 배열의 길이 1(배열의 마지막 요소를 가리키는 것)을 가리키며 mid와 요소 변수는 아직 정의되지 않았습니다.

낮은 값이 높은 값보다 작거나 같으면while 순환을 실행합니다.

우리는 중간 인덱스를 찾았다. (현재의 낮은 값과 높은 값을 더하고 나누는 것을 통해) 현재 요소를 수조에서 이 인덱스의 값으로 설정했다.만약 원소가 우리가 찾으려는 키보다 작다면, 우리는 낮은 값을 다시 성명하고, 원소가 키보다 크다면, 우리는 높은 값을 다시 성명하고 단계 2로 돌아간다.

원소의 정확한 값을 검사한다.만약 원소가 키값보다 크지도 작지도 않다면, 우리는 우리의 원소를 찾을 것이다!

만약에 우리가 순환 중에 키 값을 되돌려 주지 않는다면 이 값은 수조에 존재하지 않습니다!우리는 1 만 되돌아간다.

다음은 코드 세션에서 제공한 입력으로 이 알고리즘을 직관적으로 나타낸다.
우리의 검색치는 9이다.
우선, 우리의 중간값은 13, 9는 13보다 작기 때문에 우리는 13보다 큰 모든 값을 무시합니다!
다음 중간 값은 4입니다. 9보다 작기 때문에 4보다 작거나 같은 값은 무시합니다.
우리의 다음 중간값은 7이고, 다시 9보다 낮기 때문에, 우리는 7보다 작거나 같은 모든 값을 무시한다.
우리의 최종치는 9이다. 이것은 우리가 찾고 있는 숫자다!
이 솔루션은 결과에 필요한 시간을 "나누기"2로 나눈다.아니면 우리가 갑절로 투입하려면 한 발자국만 더 가면 해결 방안을 찾을 수 있다는 얘기다.
바이너리 검색 예

결론

우리는 대수 기호가 그렇게 무섭지 않다는 것을 증명했다. 우리는 수학 지식이 조금만 있으면 그 배후의 논리를 쉽게 파악할 수 있다.이런 복잡도를 운행하는 알고리즘은 매우 효과적이지만, 때때로 이런 복잡도는 수중의 알고리즘에 적용되지 않는다.🏆 🏆 🏆
더 많은 기사를 보려면 here