알고리즘의 복잡도를 결정하는 데 문제가 있습니다. 복잡성내 프로그램의 시간 복잡도 분석
for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++) {}
는 그것이이 개 별도의 루프를 invloves로 O (2N) 다음 코드를 이제
for(int i=0;i <n i++){} O(n)
for(int i= 0 ;i<n ;i++){ O(n^2)
for(int j=0;j<n;j++){
}
}
뭐죠?
만약 내가 j = 5에서 n으로 시작한다면?
O(2n)이 없으며 단지 O(n)입니다. 즉, n과 같은 비율로 증가합니다. 그것은 가 루프를 중첩 인 경우
, 그것은 O(n2) 것하지만 {} 빈 블록의 존재가 중첩되지 않는 것을 의미한다.
1부터 5까지의 숫자로 시작할 때 아무런 차이가 없으며 약간 더 음수의 상수를 덧붙여서도 n으로 비례합니다. 따라서 여전히 O(n)입니다.
복소수 O(n), O(cn) 및 O(n+c) (여기서, c은 상수 임)은 모두 동일합니다. 또한 일반적으로 가장 효과가 높은 용어 만 사용합니다.
보통 O(7n3 + 3n2 + 12n + 2)은 표시되지 않으며 O(n3)으로 간략화됩니다.
최종 결과는 내가 기억할 수없는 멋진 수학을 통해 2n과 같은 것을 O (n)으로 바꿀 수 있다는 것입니다. 계수는 상수로 간주됩니다. 왜냐하면 우리는 복잡성에 관심을 가지고 있고 그 문제 만 처리 할 때 가장 많은 성장을 유발하는 방정식의 부분을 조사해야합니다. 이 경우 Big O (n^2)는 방정식의 복잡성에서 가장 두드러진 요소입니다. 따라서 귀하의 알고리즘은 Big O (n)으로 간주됩니다.
제 사과, 작은 오타가 코드의 마지막 줄을 오독합니다. 귀하가 물어 본 것은 Big O (n)
예, O (n)과 같지만, 상수에 의한 곱셈은 점근 적 복잡성에서는 중요하지 않으므로 O (n)과 같습니다. 마찬가지로 5 개의 첫 번째 요소를 건너 뛰면 루프에 O (n-5) 시간이 걸리지 만 상수를 더하거나 뺄 때 상수를 곱하는 것보다 약하기 때문에 O (n)과 동일합니다. 예 : 정의에 대해서는 http://en.wikipedia.org/wiki/Big_O_notation.
O (2n)과 같은 것이 없습니다. 시간 복잡도는 알고리즘이 실제 실행 시간이 아닌 무한대로 확장되는 방법을 나타냅니다. 당신의 예제에서 두 개의 루프는 선형의 [O (n)] 시간을 의미합니다. 즉, 입력과 함께 선형 적으로 확장되므로 전체 알고리즘은 O (n)입니다.
j = 5를 시작하면 선형 적으로 비례하므로 여전히 O (n)입니다.
따라서 본질적으로 O (2n) == O (n)입니다.
높은 순서 용어의 coeffeicient이 무시 될 수
적용 시간 복잡성의 두 가지 중요한 규칙은 경우와 n의 값이 매우 큰 경우에만 ...이 있습니다.
모든 하위 용어를 igonred 수 있습니다. 이러한 가정은 매우 간단 왜
는, 예를 고려 let`s : -
은 시간 복잡도가^2 + 3N 5N 가정하자. n의 값이 매우 낮 으면 계수와 하위 차수는 n의 작은 변화에서 두드러집니다. 그러나 n의 값이 매우 크다면, 시간 복잡성에 대한 더 낮은 차수의 효과는 매우 작고, 또한 가장 높은 차수의 계수 또한 같은 방식으로 무시 될 수 있다고 가정합니다.
시간 복잡도는 n이 이론적으로 무한대에 접근 할 때만 중요한 역할을합니다.
복잡도는 관계 입력 n 및 시간을 설명하는 함수 모양의 측정입니다.
대부분의 경우 상수를 알지 못하기 때문에 상수가 아니라는 점에 유의하십시오. 두 개의 비교 가능한 알고리즘을 비교하면 상수를 사용할 수 있지만 대부분의 경우 일반적인 복잡도를 인용하고 일부 입력을 시간을 측정합니다. 2 * O (n)은 그다지 말하는 것이 아니므로 상수 2를 사용하여 비교할 수 있기 때문에 O (2 * n)은 2 * O (n)과 동일합니다. 연산. 두 번째 알고리즘의 복잡도가 2 * O (n)이라면별로 의미가 없습니다.
이런 식으로 복잡성을 조사하십시오.
당신은 n = 1 백만을받는 알고리즘을 가지고 있다고 가정 해 보겠습니다. 동작 횟수 대략적인 크기 또는 주문시 비트 내가 생각에서 얻는 것은 (I = 0; i가 N <; 내가 ++)을위한 혼돈
O(n) -> 1e6 and this can be calculated in most cases
O(n * log(n)) -> 2*1e7 this can also be calculated in reasonable time.
O(n^2) -> 1e12 you will not be able to compute whit this algorithm in reasonable time
O(n^3) -> 1e18 here are so many operations that you have to think twice on how you are going to aproach this problem
란, N J <(j = 0 {} ; j ++) {}는 O (n)입니까? 그들은 중첩되지 않은 루프입니다 – jslearner