입력 크기에 따라 다음 패턴을 따르는 Big-O 표기법에서 알고리즘의 계산 복잡성을 어떻게 지정할 수 있습니까? 이 때문에Big-O 표기법의 연산 복잡성
Input size: 4
Number of execution steps: 4 + 3 + 2 + 1 = 10
Input size: 5
Number of execution steps: 5 + 4 + 3 + 2 + 1 = 15
Input size: 6
Number of execution steps: 6 + 5 + 4 + 3 + 2 + 1 = 21
기술적으로 복잡성을 결정하기에 충분한 정보를 제공하지 않았습니다. 지금까지의 정보에서는 5보다 큰 모든 입력 크기에 대해 21 단계를 취할 수있었습니다.이 경우 크기 4 및 5에 대한 동작과 관계없이 O (1)이됩니다. 복잡성은 큰 입력 크기, 아주 작은 세 가지 크기에 대해 어떻게 행동해야하는지에 관한 것이 아닙니다.
크기 n의 단계 수를 일반적으로 1에서 n까지의 숫자의 합계이면 단계 수에 대한 공식은 실제로 n (n + 1)/2이고 O (n^2).
나는 그것이 O(N)해야한다고 생각처럼 : N의 크기와 배열을 지정해, 그리고 (우리는 더하기 계산 시간을 신경 쓰지 않는 경우)을 반복.
덧붙여서 (n + 1)*n/2은 단지 알고리즘의 복잡성이 아니라 합계의 결과라고 생각합니다.
패턴 1 + 2 + 3 + 4 + ... + n 다음에 나오는 시리즈의 경우, 시리즈의 합은 n (n + 1)/2로 주어지며, 이는 O (n^2) ..
각 단계에서 우리가 한 단계 (n + n-1 + n-2)를 덜하기 때문에 단계 수가 n^2가되지 않지만 큰 오 표기법은 따라서 함수의 증가율에 대한 상한을 지정하는 데 사용되므로 큰 O는 n 단계 이상이지만 n^2 단계 미만이므로 O (n^2)가됩니다.
수식이 (n + 1) * n/2이므로 O (n^2)입니다. – nhahtdh