[time-complexity] O (log n)은 정확히 무엇을 의미합니까?

개요

다른 사람들은 트리 다이어그램과 같은 좋은 다이어그램 예제를 제공했습니다. 간단한 코드 예제는 보지 못했습니다. 따라서 내 설명 외에도 다양한 알고리즘 범주의 복잡성을 설명하기 위해 간단한 인쇄 문이있는 알고리즘을 제공합니다.

먼저 https://en.wikipedia.org/wiki/Logarithm 에서 얻을 수있는 Logarithm에 대한 일반적인 아이디어가 필요합니다 . 자연 과학 사용 e과 자연 로그. 공학자들은 컴퓨터가 이진 기반이기 때문에 log_10 (로그베이스 10)을 사용하고 컴퓨터 과학자들은 log_2 (로그베이스 2)를 많이 사용합니다. 때로는 자연 로그의 약어가로 표시 ln()되고 엔지니어는 일반적으로 _10을 끄고 사용하면 log()log_2는로 표시됩니다 lg(). 모든 유형의 로그는 비슷한 방식으로 성장하므로 동일한 카테고리를 공유합니다 log(n).

아래 코드 예제를 볼 때 O (1), O (n), O (n ^ 2)를 확인하는 것이 좋습니다. 당신이 그것들을 잘 알고 나면 다른 것들을보십시오. 미묘한 변화가 여전히 동일한 분류를 초래할 수있는 방법을 보여주는 변형뿐만 아니라 깨끗한 예를 포함 시켰습니다.

O (1), O (n), O (logn) 등을 클래스 또는 성장 범주로 생각할 수 있습니다. 일부 카테고리는 다른 카테고리보다 시간이 더 걸립니다. 이 범주는 알고리즘 성능을 주문하는 방법을 제공합니다. 일부는 입력 n이 증가함에 따라 더 빠르게 성장했습니다. 하기 표는 상기 성장을 수치 적으로 설명한다. 아래 표에서 log (n)을 log_2의 상한값으로 생각하십시오.

다양한 Big O 카테고리의 간단한 코드 예제 :

O (1)-상수 시간 예 :

• 알고리즘 1 :

알고리즘 1은 hello를 한 번 인쇄하며 n에 의존하지 않으므로 항상 일정한 시간에 실행되므로입니다 O(1).

print "hello";

• 알고리즘 2 :

알고리즘 2는 hello를 3 번 ​​인쇄하지만 입력 크기에 의존하지 않습니다. n이 커지더라도이 알고리즘은 항상 hello를 3 번만 인쇄합니다. 3이라고하는 것은 상수 이므로이 알고리즘도 마찬가지 O(1)입니다.

print "hello";
print "hello";
print "hello";

O (log (n))-대수 예제 :

• 알고리즘 3- “log_2″와 같은 역할

알고리즘 3은 log_2 (n)에서 실행되는 알고리즘을 보여줍니다. for 루프의 포스트 연산은 i의 현재 값에 2를 곱하므로 i1에서 2로, 4에서 8로, 16에서 32로갑니다.

for(int i = 1; i <= n; i = i * 2)
  print "hello";

• 알고리즘 4- “log_3″과 같은 기능

알고리즘 4는 log_3을 보여줍니다. 통지 i는 1에서 3으로, 9에서 27로갑니다 …

for(int i = 1; i <= n; i = i * 3)
  print "hello";

• 알고리즘 5- “log_1.02″와 같은 기능

알고리즘 5는 숫자가 1보다 크고 결과가 반복해서 자신에 대해 곱해지는 한, 로그 알고리즘을보고 있다는 것을 보여 주므로 중요합니다.

for(double i = 1; i < n; i = i * 1.02)
  print "hello";

O (n)-선형 시간 예 :

• 알고리즘 6

이 알고리즘은 간단하며 hello를 n 번 인쇄합니다.

for(int i = 0; i < n; i++)
  print "hello";

• 알고리즘 7

이 알고리즘은 hello n / 2 번 인쇄되는 변형을 보여줍니다. n / 2 = 1/2 * n. 1/2 상수를 무시하고이 알고리즘이 O (n)임을 알 수 있습니다.

for(int i = 0; i < n; i = i + 2)
  print "hello";

O (n * log (n))-nlog (n) 예 :

• 알고리즘 8

(A)의 조합이 생각 O(log(n))하고 O(n). for 루프의 중첩은 우리가O(n*log(n))

for(int i = 0; i < n; i++)
  for(int j = 1; j < n; j = j * 2)
    print "hello";

• 알고리즘 9

알고리즘 9는 알고리즘 8과 비슷하지만 각 루프마다 변형이 허용되어 최종 결과는 여전히 O(n*log(n))

for(int i = 0; i < n; i = i + 2)
  for(int j = 1; j < n; j = j * 3)
    print "hello";

O (n ^ 2)-n 제곱 예 :

• 알고리즘 10

O(n^2) 표준 for 루프를 중첩하여 쉽게 얻을 수 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    print "hello";

• 알고리즘 11

알고리즘 10과 유사하지만 약간의 변형이 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j = j + 2)
    print "hello";

O (n ^ 3)-n 큐브 형 예 :

• 알고리즘 12

이것은 알고리즘 10과 비슷하지만 2 대신 3 개의 루프가 있습니다.

for(int i = 0; i < n; i++)
  for(int j = 0; j < n; j++)
    for(int k = 0; k < n; k++)
      print "hello";

• 알고리즘 13

알고리즘 12와 유사하지만 여전히 변형되는 변형이 있습니다 O(n^3).

for(int i = 0; i < n; i++)
  for(int j = 0; j < n + 5; j = j + 2)
    for(int k = 0; k < n; k = k + 3)
      print "hello";

요약

위의 몇 가지 간단한 예제와 분석을 변경하지 않는 미묘한 변경 사항을 소개하는 변형을 보여줍니다. 잘하면 그것은 당신에게 충분한 통찰력을 제공합니다.

답변

1 millisecond to complete if you have 2 elements.
2 milliseconds to complete if you have 4 elements.
3 milliseconds to complete if you have 8 elements.
4 milliseconds to complete if you have 16 elements.
...
n milliseconds to complete if you have 2^n elements.