1. дома
  2. Вопрос и ответ
  3. Порядок роста следующих функций

Порядок роста следующих функций

2016-04-17 4 views
-4

, относящийся к qn ниже, в порядке возрастания роста: g2, g3, g4, g1, g5? g2 = 4n, g3 = 18nlgn, g4 = 12n^2LG (п-1) , g1 = 25N^2lgn, g5 = 15n^3Порядок роста следующих функций

enter image description here

источник

2016-04-17 blackhazelnut

+1

Можете ли вы показать свою попытку решить эту проблему или что вы пробовали? Люди здесь более чем готовы/могут помочь, но это не где-то просто получить бесплатные ответы на домашнюю работу без каких-либо усилий. –

+0

Я записываю упрощенную форму каждой функции. – blackhazelnut

+1

Не только вопрос о домашнем задании, но и фактически скопировал вопрос из книги! Послушайте, @ SIRO1690, давая вам ответ, никоим образом не поможет вам. – gnasher729

ответ

2

Этот вопрос требует, чтобы использовать некоторую алгебру, чтобы трансформировать функции, так что вы можете сравнить их. Помните, что ведущие константы не имеют значения для асимптотических сравнений. Основания экспоненты/логарифма иногда do вопрос, хотя, поэтому будьте осторожны с ними.

  • g1(n) = n^2 lg n, используя approximationlg n! ~ n lg n.
  • g2(n) = 4^(lg n) = n^(lg 4) << n^2, предполагая lg база e.
  • g3(n) = n^2 lg n с использованием formula на сумму арифметической прогрессии.
  • g4(n) = n^2 (lg lg n)^2
  • g5(n) = n^3

На данный момент, вы можете использовать тот факт, что lg n^k << n для любого фиксированного k. Это означает, что более высокая мощность n доминирует над более высокой мощностью lg n. Аналогично (lg lg n)^k << lg n для любых k.

Выполнение данного запроса g2 << g4 << g1 = g3 << g5.

источник

2016-04-18 05:01:40 augurar

1

Вы можете перепроверить, как я считаю, результаты: g2 g4 g3 g5 g1

Вот C программа, которая проверяет функции. Вы должны дважды проверить программу [в основном функции g*] и g4 в частности. Итак, вот оно:

#include <stdio.h> 
#include <stdlib.h> 
#include <math.h> 

#define FLT long double 

struct rtn { 
    const char *name; 
    FLT val; 
}; 
typedef struct rtn rtn_t; 

#define DO(_alg) \ 
    do { \ 
     ptr = &list[_alg - 1]; \ 
     g##_alg(ptr,n); \ 
     printf("%s: %Lg\n",ptr->name,ptr->val); \ 
    } while (0) 

FLT 
fact(unsigned long long n) 
{ 
    unsigned long long i; 
    FLT f; 

    f = 1.0; 

    for (i = 1; i <= n; ++i) { 
     f *= n; 
    } 

    return f; 
} 

void 
g1(rtn_t *rtn,unsigned long long n) 
{ 
    FLT val; 

    rtn->name = "g1"; 

    val = 25.0; 
    val *= n; 
    val *= logl(fact(n)); 

    rtn->val = val; 
} 

void 
g2(rtn_t *rtn,unsigned long long n) 
{ 
    FLT val; 

    rtn->name = "g2"; 

    val = logl(n); 
    val += val; 
    val = powl(2,val); 

    rtn->val = val; 
} 

void 
g3(rtn_t *rtn,unsigned long long n) 
{ 
    FLT val; 
    FLT lgn; 
    unsigned long long k; 

    rtn->name = "g3"; 

    lgn = logl(n); 

    val = 0; 

    for (k = 1; k <= n; ++k) 
     val += lgn * k; 

    val *= 18; 

    rtn->val = val; 
} 

void 
g4(rtn_t *rtn,unsigned long long n) 
{ 
    FLT val; 
    FLT lgn; 

    rtn->name = "g4"; 

    val = n; 
    val *= val; 
    val *= 12; 

    lgn = logl(n); 
    lgn = logl(lgn); 
    lgn *= lgn; 

    val *= lgn; 

    rtn->val = val; 
} 

void 
g5(rtn_t *rtn,unsigned long long n) 
{ 
    FLT val; 

    rtn->name = "g5"; 

    val = n; 
    val = val * val * val; 

    val *= 15; 

    rtn->val = val; 
} 

int 
cmp(const void *lhs,const void *rhs) 
{ 
    const rtn_t *lp; 
    const rtn_t *rp; 
    int cmpflg; 

    lp = lhs; 
    rp = rhs; 

    do { 
     cmpflg = 0; 

     if (lp->val < rp->val) { 
      cmpflg = -1; 
      break; 
     } 

     if (lp->val > rp->val) { 
      cmpflg = 1; 
      break; 
     } 
    } while (0); 

    return cmpflg; 
} 

void 
order(unsigned long long n) 
{ 
    rtn_t list[5]; 
    rtn_t *ptr; 

    printf("\n"); 
    printf("n: %llu\n",n); 

    DO(1); 
    DO(2); 
    DO(3); 
    DO(4); 
    DO(5); 

    qsort(list,5,sizeof(rtn_t),cmp); 

    for (ptr = list; ptr < &list[5]; ++ptr) 
     printf(" %s",ptr->name); 
    printf("\n"); 

    fflush(stdout); 
} 

int 
main(void) 
{ 
    unsigned long long n; 

    n = 1; 
    for (n = 1; n < (1LL << 62); n *= 2) 
     order(n); 

    return 0; 
}

Вот результат работы программы:

n: 1 
g1: 0 
g2: 1 
g3: 0 
g4: inf 
g5: 15 
g1 g3 g2 g5 g4 

n: 2 
g1: 69.3147 
g2: 2.61406 
g3: 37.4299 
g4: 6.44792 
g5: 120 
g2 g4 g3 g1 g5 

n: 4 
g1: 554.518 
g2: 6.83333 
g3: 249.533 
g4: 20.4845 
g5: 960 
g2 g4 g3 g1 g5 

n: 8 
g1: 3327.11 
g2: 17.8628 
g3: 1347.48 
g4: 411.625 
g5: 7680 
g2 g4 g3 g1 g5 

n: 16 
g1: 17744.6 
g2: 46.6944 
g3: 6787.3 
g4: 3194.74 
g5: 61440 
g2 g4 g3 g1 g5 

n: 32 
g1: 88722.8 
g2: 122.062 
g3: 32938.4 
g4: 18983.3 
g5: 491520 
g2 g4 g3 g1 g5 

n: 64 
g1: 425870 
g2: 319.078 
g3: 155709 
g4: 99843.8 
g5: 3.93216e+06 
g2 g4 g3 g1 g5 

n: 128 
g1: 1.98739e+06 
g2: 834.091 
g3: 721051 
g4: 490438 
g5: 3.14573e+07 
g2 g4 g3 g1 g5 

n: 256 
g1: 9.08522e+06 
g2: 2180.37 
g3: 3.28345e+06 
g4: 2.30749e+06 
g5: 2.51658e+08 
g2 g4 g3 g1 g5 

n: 512 
g1: 4.08835e+07 
g2: 5699.62 
g3: 1.47468e+07 
g4: 1.05429e+07 
g5: 2.01327e+09 
g2 g4 g3 g1 g5 

n: 1024 
g1: 1.81704e+08 
g2: 14899.2 
g3: 6.54775e+07 
g4: 4.71655e+07 
g5: 1.61061e+10 
g2 g4 g3 g1 g5 

n: 2048 
g1: inf 
g2: 38947.4 
g3: 2.8796e+08 
g4: 2.07694e+08 
g5: 1.28849e+11 
g2 g4 g3 g5 g1 

n: 4096 
g1: inf 
g2: 101811 
g3: 1.25625e+09 
g4: 9.03472e+08 
g5: 1.03079e+12 
g2 g4 g3 g5 g1 

n: 8192 
g1: inf 
g2: 266140 
g3: 5.44307e+09 
g4: 3.89214e+09 
g5: 8.24634e+12 
g2 g4 g3 g5 g1 

n: 16384 
g1: inf 
g2: 695707 
g3: 2.34457e+10 
g4: 1.66359e+10 
g5: 6.59707e+13 
g2 g4 g3 g5 g1 

n: 32768 
g1: inf 
g2: 1.81862e+06 
g3: 1.00478e+11 
g4: 7.06453e+10 
g5: 5.27766e+14 
g2 g4 g3 g5 g1 

n: 65536 
g1: inf 
g2: 4.754e+06 
g3: 4.28701e+11 
g4: 2.98373e+11 
g5: 4.22212e+15 
g2 g4 g3 g5 g1 

n: 131072 
g1: inf 
g2: 1.24273e+07 
g3: 1.82197e+12 
g4: 1.25439e+12 
g5: 3.3777e+16 
g2 g4 g3 g5 g1 

n: 262144 
g1: inf 
g2: 3.24856e+07 
g3: 7.71653e+12 
g4: 5.2528e+12 
g5: 2.70216e+17 
g2 g4 g3 g5 g1 

n: 524288 
g1: inf 
g2: 8.49195e+07 
g3: 3.25808e+13 
g4: 2.19211e+13 
g5: 2.16173e+18 
g2 g4 g3 g5 g1 

n: 1048576 
g1: inf 
g2: 2.21985e+08 
g3: 1.37182e+14 
g4: 9.12084e+13 
g5: 1.72938e+19 
g2 g4 g3 g5 g1 

n: 2097152 
g1: inf 
g2: 5.80283e+08 
g3: 5.76166e+14 
g4: 3.78499e+14 
g5: 1.38351e+20 
g2 g4 g3 g5 g1 

n: 4194304 
g1: inf 
g2: 1.5169e+09 
g3: 2.41441e+15 
g4: 1.56705e+15 
g5: 1.1068e+21 
g2 g4 g3 g5 g1 

n: 8388608 
g1: inf 
g2: 3.96527e+09 
g3: 1.00966e+16 
g4: 6.47442e+15 
g5: 8.85444e+21 
g2 g4 g3 g5 g1 

n: 16777216 
g1: inf 
g2: 1.03655e+10 
g3: 4.21424e+16 
g4: 2.66999e+16 
g5: 7.08355e+22 
g2 g4 g3 g5 g1 

n: 33554432 
g1: inf 
g2: 2.7096e+10 
g3: 1.75593e+17 
g4: 1.09924e+17 
g5: 5.66684e+23 
g2 g4 g3 g5 g1 

n: 67108864 
g1: inf 
g2: 7.08306e+10 
g3: 7.30468e+17 
g4: 4.51869e+17 
g5: 4.53347e+24 
g2 g4 g3 g5 g1 

n: 134217728 
g1: inf 
g2: 1.85156e+11 
g3: 3.03425e+18 
g4: 1.85497e+18 
g5: 3.62678e+25 
g2 g4 g3 g5 g1 

n: 268435456 
g1: inf 
g2: 4.84009e+11 
g3: 1.25865e+19 
g4: 7.60524e+18 
g5: 2.90142e+26 
g2 g4 g3 g5 g1 

n: 536870912 
g1: inf 
g2: 1.26523e+12 
g3: 5.21442e+19 
g4: 3.11451e+19 
g5: 2.32114e+27 
g2 g4 g3 g5 g1

источник

2016-04-18 04:10:12

+0

Экспериментальные результаты могут быть не такими полезными при определении поведения на бесконечности. – augurar

+1

@augurar Возможно. Но они предоставляют другую контрольную точку [для OP]. Мои результаты противоречат его. Он может решить, изменились ли значения для _very_ больших 'n' [за пределами того, что я подсчитал]. Я не добавлял никакого кода для сравнения относительных темпов расхождения. Вероятно, это проявится достаточно рано. Я был слишком ленив, чтобы использовать «GMP» и тестировать одно [несколько] _large_ 'n' значений (например,' n = 1e5000') –

+0

На самом деле это неправильно. Асимптотически "g2 << g4 << g1 = g3 << g5'. – augurar

Смежные вопросы

 Смежные вопросы