O (n)과 O (log (n))의 차이점-어느 것이 더 낫고 정확히 O (log (n))는 무엇입니까?

O (n)과 O (log (n))의 차이점-어느 것이 더 낫고 정확히 O (log (n))는 무엇입니까?

---

이것은 데이터 구조와 모든 강의 / TA 강의에 대한 저의 첫 번째 과정입니다 O(log(n)). 이것은 아마도 어리석은 질문이지만 누군가가 그것이 무엇을 의미하는지 정확히 설명해 주시면 감사하겠습니다!?

---

이는 해당 항목 (일반적으로 실행 시간)이 입력 크기의 로그와 일치하는 방식으로 확장된다는 것을 의미합니다.

Big-O 표기법 은 정확한 방정식이 아니라 경계를 의미합니다 . 예를 들어, 다음 함수의 출력은 모두 O (n)입니다.

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

- 당신은 X 증가로, 자신의 출력을 선형 적으로 모두 증가하기 때문에 거기에 6의 경우 : 사이 1의 비율 f(n)과 g(n)사이 : 1의 비율로, 또한 약 6가있을 것입니다 f(10*n)및 g(10*n)등등.

---

에 관해서 여부 O(n)또는 O(log n)인 더 고려 : 만약 n = 1000다음, log n = 3(로그 기반-10). 알고리즘을 실행하는 데 1000 초 또는 3 초가 더 필요합니까?

---

크기 입력의 n경우의 알고리즘은에 O(n)비례하는 단계를 수행 n하고 다른 알고리즘은 O(log(n))대략적인 단계를 수행합니다 log(n).

분명히 log(n)보다 작은 n따라서 복잡한 알고리즘이 O(log(n))좋다. 훨씬 빠를 것이기 때문에.

---

짧은 대답의 경우 O (log n)가 O (n)보다 낫습니다.

이제 정확히 O (log n)은 무엇입니까?

일반적으로 big O 표기법을 참조 할 때 log n 은 밑이 2 인 로그를 나타냅니다 (같은 방식으로 ln이 밑이 e 로그를 나타냄). 이 밑이 2 인 로그는 지수 함수의 역입니다. 지수 함수 는 매우 빠르게 성장하고 우리는 역이 정반대를 할 것이라고 직관적으로 추론 할 수 있습니다 . 즉 매우 느리게 성장 합니다.

예를 들면

x = O (로그 n)

n을 다음과 같이 나타낼 수 있습니다.

n = 2 ^x

과

2 ¹⁰ = 1024 → lg (1024) = 10

2 ²⁰ = 1,048,576 → lg (1048576) = 20

2 ³⁰ = 1,073,741,824 → lg (1073741824) = 30

대형 단위 N 에만 로그에 매우 작은 증가로 이어질 (N)

반면에 O (n)의 복잡성에 대해 우리는 선형 관계를 얻습니다.

log ₂ n의 계수는 언제든지 n의 계수를 인수해야합니다.

이를 더욱 확고히하기 위해 저는 Thomas Cormen의 알고리즘 잠금 해제 에서 예를 보았습니다.

두 대의 컴퓨터를 고려하십시오 : A와 B

두 컴퓨터 모두 배열에서 값을 검색하는 작업이 있습니다. 배열에 1,000 만 개의 요소가 검색되어야한다고 가정 해 보겠습니다.

컴퓨터 A-이 컴퓨터는 초당 10 억 개의 명령을 실행할 수 있으며 복잡도가 O (n) 인 알고리즘을 사용하여 위의 작업을 수행 할 것으로 예상됩니다. 이 컴퓨터가 작업을 완료하는 데 걸리는 시간을 대략적으로 추정 할 수 있습니다.

n / (지시 p 초) → 10 ⁷ / 10 ^ 9 = 0.01 초

컴퓨터 B-이 컴퓨터는 훨씬 더 느리고 초당 천만 명령 만 실행할 수 있습니다. 컴퓨터 B는 복잡성이 O (log n) 인 알고리즘을 사용하여 위의 작업을 수행 할 것으로 예상됩니다. 이 컴퓨터가 작업을 완료하는 데 걸리는 시간을 대략적으로 추정 할 수 있습니다.

log (n) / (명령 p 초) → log (10 ⁷ ) / 10 ⁷ = 0.000002325349

이 그림을 통해 컴퓨터 A가 컴퓨터 B보다 훨씬 낫지 만 B가 사용하는 알고리즘으로 인해 작업이 훨씬 더 빨리 완료된다는 것을 알 수 있습니다.

O (log (n))가 O (n)보다 훨씬 빠른 이유가 이제 매우 명확해야한다고 생각합니다.

---

http://en.wikipedia.org/wiki/Big_oh

O (log n)가 더 좋습니다.

---

O (logn)는 알고리즘의 최대 실행 시간이 입력 크기의 로그에 비례 함을 의미합니다. O (n)은 알고리즘의 최대 실행 시간이 입력 크기에 비례 함을 의미합니다.

기본적으로 O (무언가)는 알고리즘의 명령어 수 (원자 수)의 상한입니다. 따라서 O (logn)은 O (n)보다 타이트하고 알고리즘 분석 측면에서도 더 좋습니다. 그러나 O (logn) 인 모든 알고리즘도 O (n)이지만 역방향은 아닙니다 ...

---

공식적인 정의 :

g (x) = O (f (x)) <=> x> x0, | g (x) |에 대해 x0과 상수 C가 있습니다. <= C | f (x) |.

따라서 복잡도가 O (f (n)) 인 문제 P에 대한 알고리즘 A를 찾으면 알고리즘이 수행 할 단계 수가 점근 적으로 f (n)보다 낮거나 같다고 말할 수 있습니다. 입력 크기. (n은 무엇이든 될 수 있음)

추가 정보 : http://en.wikipedia.org/wiki/Big_O_notation.

참조 URL : https://stackoverflow.com/questions/10369563/difference-between-on-and-ologn-which-is-better-and-what-exactly-is-olo