기능의 시간 복잡도는 어느 정도입니까?

기능의 시간 복잡도는 어느 정도입니까?

이 질문에는 이미 답변이 있습니다.

알고리즘의 시간 복잡도는 어떻게 찾을 수 있습니까? (9개의 답변)

Big O, 어떻게 계산/근사합니까? (24 회답)

고조파 급수의 빅 O 찾기 (2개의 답변)

닫힘4년 전에요.

복잡성에 대해 공부하기 시작했는데, 이것 때문에 고민하고 있어요.

void what(int n) {
    int i;
    for (i = 1; i <= n; i++) {
        int x = n;
        while (x > 0)
            x -= i;
    }
}

첫 번째 포루프는 확실히O(n) 번째 은 " " " 입니다O(n), 두 번째, 두 번째 입니다O(n/2)..그리고 그렇게log(n)몇 번인가?그 말은. 내가 제대로 한 거야?

편집: (복제가 아님) Big O가 뭔지 알고 있습니다.특정 사례에 대한 올바른 평가를 요청했습니다.

는 외측 루프를 통과합니다.ntimesdiscloss.discloss를 합니다.

루프가 됩니다.n / itimesdiscloss.discloss를 합니다.

총 런 수는 다음과 같습니다.

n + n/2 + n/3 + ... + n/n

점근적으로(정수 산술 반올림 무시) 이것은 다음과 같이 단순화된다.

n * (1 + 1/2 + 1/3 + ... + 1/n)

되어 있다.n * log(n).

따라서 복잡도는 예상대로 O(N.log(N)입니다.

합니다.y = n - x 표기 뒤에 표기법을 반복 합니다.while루프를 설정합니다.

상기에서는 각 내부 while 루프에 대해 반복 횟수를 다음과 같이 과대평가하고 있습니다.1의 경우n-1는 의 .i서, ,, 소(n-1) % i != 0'이렇게 하다', '이렇게 하다', 가정해 보겠습니다.(n-1)/i는 모든 입니다.i가 과대평가되어 있습니다.while를 less or equal 부호를 (i)시그마로 하겠습니다.

we우에서(ii) 「」의 근사치를 .n: 연관된 적분에 의한 고조파 수.따라서 알고리즘이 실행된다.O(n·ln(n)) 점근적으로.

---

할 수 .(n,cnt)서 (어디서)cnt 참조에 의한 횟수) chux(반복 횟수)와합니다.n(1+ln(n))-ln(n)실제 숫자에 대해서는 아래 그림이나 이 스니펫을 참조해 주십시오.

---

으로, 「 」를 「 」로 하면, 「 」가 되는 해 주세요.n->∞1/i위의 결과 급수는 무한 고조파 급수이며, 이상하게도 충분히 발산적이다.후자의 증거는 0이 아닌 항의 무한합에서 자연스럽게 무한하다는 사실을 이용한다.그러나 실제로는 충분히 크지만 무한하지 않은 n에 대해서는ln(n)는 합계의 적절한 근사치이며, 이 차이는 여기서의 점근 분석과는 관련이 없습니다.

---

첫 번째 내부 루프가 실행됩니다.n시대
두 번째 내부 루프가 작동합니다.n/2시대
세 번째 내부 루프가 작동합니다.n/3시대
..마지막은 한 번 달린다.

그렇게n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n).

이 n에 고조파 급수의 합을 곱하면 닫힌 형태 표현이 좋지 않습니다.하지만 여기 보이는 것처럼O(log(n))은 전체적으로 ''입니다O(n log(n))

테스트와 그래픽스를 통해 이를 시도합니다.log2 대 log2 그림은 상당히 선형으로 보입니다.선형 O(n)보다 크고 O(n*log(n)보다 작은 것. 자신의 결론을 도출합니다.

[편집]

수학적으로 도출된 수식을 사용하여 계산된 O()는 O(n * log(n))의 상한입니다.는 카운트를 1이 시키는 '의 분할를 들어 1은 '루프 반복의 분할'입니다.n입니다. + + + 1.5 7 6 + 3 ++ 1=. 7 루프는 .반복 횟수는 6 + 3 + 2 + 1.5 + 1 = 14.7 루프를 나타냅니다. 덜 중요하다.nO(n * log(n))이다그래서 코드를 정수 수학으로 사용하는 것을 무시하지 않음으로써, 우리는 훨씬 더 어려운 질문을 하게 됩니다.

---

unsigned long long what(int n) {
  unsigned long long cnt = 0;
  int i;
  for (i = 1; i <= n; i++) {
    int x = n;
    while (x > 0) {
      x -= i;
      cnt++;
    }
  }
  return cnt;
}

void wtest(int n) {
  unsigned long long cnt = what(n);
  printf("%d %llu\n", n, cnt);
  fflush(stdout);
}

void wtests(void) {
  int i = INT_MAX/2 + 1;
  while (i > 0) {
    wtest(i);
    i /= 2;
  }
}

int main(void) {
  wtests();
  return 0;
}

산출량

1073741824 23567395117
536870912 11411566988
268435456 5519718329
134217728 2666826555
67108864 1286897093
33554432 620190504
16777216 298466265
8388608 143418602
4194304 68802063
2097152 32947406
1048576 15746897
524288 7510048
262144 3573331
131072 1695816
65536 802493
32768 378537
16384 177921
8192 83286
4096 38803
2048 17973
1024 8275
512 3782
256 1713
128 765
64 337
32 145
16 61
8 24
4 9
2 3
1 1

언급URL : https://stackoverflow.com/questions/35326140/what-is-the-time-complexity-of-my-function