O (n^2) 대 O (n)의 알고리즘

Question

저는 컴퓨터 과학을 처음 접했고 의사 코드로 시작했고 몇 가지 질문이 있습니다. 그것은 학기 내 제 3 주이고 대다수는 스스로 공부하고 있습니다. 몇 가지 질문이 있습니다.

O (n^2) 알고리즘과 O (n) 알고리즘의 차이점은 무엇입니까? - 마찬가지로 O (n log n)입니까? - 및 Ω (n^2)?

horner = 0; 
for(i = n; i >= 0; i −−) 
    horner = x * horner + a[i]; 

을하지만 (n)이 O입니다 발견 :

은 지금까지 내가 작성했습니다. 어떻게 변환합니까?

런타임은 무엇입니까? - 첫 번째 줄의 할당은 1 작업임을 알고 있습니다.

그리고 실제로 C# 알고리즘과 어떻게 다릅니 까?

Answer 1

O (N)은 반복, 계산의 개수를 나타낸다 또는 그 최종 상태에 도달하기 위해 알고리즘,가 대부분 (최악)에서 필요 걸음 n는 객체의 시작시 주어지는 알고리즘

5 개의 요소로 구성된 배열과 O (n^2) 개의 복잡성을 갖는 정렬 알고리즘이 있다고 가정 해 보겠습니다. 배열에 정렬을 적용하면 끝 상태에 도달하는 데 최대 5^2 = 25 단계가 필요하다는 것을 알고 있습니다.

는 또한 읽기 : What is the difference between O, Ω, and Θ?

Answer 2

이 무슨 요구하는 것은 알고리즘의 복잡성 분석으로 알려진 컴퓨터 과학의 주제입니다. 런타임이나 계산 속도와 관련이 있기 때문에 프로그램에 알고리즘이나 솔루션을 작성할 때 고려해야 할 매우 중요한 주제입니다.

Big-Oh 또는 O (n)은 알고리즘 실행을위한 상한 실행 시간과 관련이 있습니다. 이 경우, O (n)은 n 요소를 의미하며, 알고리즘 계산을 위해 고려 된 모든 n 요소가 필요하거나 선형이 필요합니다. 이 Big-Oh 복잡도의 범위는 매우 크고 매우 느린 계산을 위해 일정 시간, O (1)부터 위로 O (n^n)까지입니다. 또한, 다음과 같은 방정식을 고려

y=10n+1 
y=5n+10 

이 모두 O (n)의 복잡성으로 인해 소자의 수가 증가, 식 큰 그것 때문에 더 증가한다. 방정식은 변화하지 않는 상수 값 때문이 아니라 변수로 인해 방정식이 더 커지고 빠르게 증가하기 때문에 상수를 무시합니다. 반면, 다음과 같은 식 :

복잡도가 10N^2 수학 빠른 성장에 기여하는 가장 큰 요소 인 성장에 의한 O (N^2) 될 것이다

y=10n^2+5n+5 

. 우리는 상수를 버리고 복잡성을 평가하는 방정식으로 성장하는 가장 큰 구성 요소를 고려합니다.

빅 오메가 복잡도의 경우 알고리즘 복잡도 분석의 하한으로 간주합니다. 예를 들어, 알고리즘은 Omega (n) (가장 좋은 경우)만큼 빠르게 실행할 수 있지만 O (n^2) (최악의 경우)만큼 오래 걸릴 수 있습니다. 이는 정렬 알고리즘 또는 검색 알고리즘을 분석하는 데 일반적입니다.

우리는 더 빠른 솔루션이나 더 빠른 실행을 위해 더 빠른 프로그램을 원할 때 특히 최적화를 위해 효율적이고 빠른 알고리즘을 사용하여 프로그램을 작성하고자합니다.

제공 한 코드 예제는 for 루프를 사용하여 n 요소를 반복하기 때문에 O (n)입니다. 현재 for 루프 내에 두 번째 루프가있는 double for 루프를 생각해보십시오. 이것은 최악의 경우, n * n 요소를 반복하기 때문에 O (n^2)입니다. 빈 행렬을 초기화 O (N^2) 런타임 용

자바 의사 코드 :

int result[n][m]; 
for(int i=0; i<n; ++i){ 
    for(int j=0; j<m; ++j){ 
     result[i][j] = 0; 
    } 
} 

통지, 그것을 따라서 O (N^2) 런타임 유도 두 개의 루프를 사용한다. 여기

방정식은 시간이 지남에 따라 성장하는 방법을 보여주는 그래프이다 : 거의 정확히 C의 # 구문의 그