插入排序擊敗歸併排序N <= 8logn，正

-3

ň< = 8logn如何解決這個方程得到n的值，

的問題是從algorith 「對於大小爲n的輸入，插入排序在8N^2個步驟運行而歸併排序在64N LG n步運行;其中對於n值並插入排序擊敗歸併排序

所以我想直到..

8n^2<=64nlogn

N^2 = < 8nlogn ň< = 8logn

，但如何從這裏得到的n值，全數學將是有益的任何鏈接，瞭解基本的數學logarith表示讚賞。謝謝

來源

2015-09-20 Mansur Ahamed

http://www.wolframalpha.com/input /？i = n +％3C + 8 + logn –

我正在投票結束這個問題，因爲它是關於mat Hematics，而不是編程。 –

我們必須弄清楚，對於哪個值n,8n^2和64nlogn具有相同的值。所以，

8n^2 = 64nlogn 
=> n = 8logn 
=> n = log (n^8) 
=> 2^n = n^8

現在用的幫助循環，我們可以從n=2重複，以用於其2^n = n^8數。

// language cpp 
#include <iostream> 
#include <math.h> 

using namespace std; 

int main() 
{ 
    double n = 2; 

    while(pow(2, n) < pow(n, 8)){ 
     cout << "n = " << n << endl; 
     cout << "2^n = " << (long long) pow(2,n) << endl; 
     cout << "n^8 = " << (long long) pow(n,8) << endl; 
     cout << endl; 
     n++; 
    } 

    cout << "n = " << n << endl; 
    cout << "2^n = " << (long long) pow(2,n) << endl; 
    cout << "n^8 = " << (long long) pow(n,8) << endl; 

    return 0; 
}

從輸出中，我們看到的值是在43號和44

有關對數的基本知識之間，你可以去Khan Academy Lectures on Logarithm。

來源

2015-09-20 13:26:56

你能解釋最後2行=> n = log（n^8） => 2^n = n^8，這是怎麼完成的？ –

也在代碼中爲什麼你開始n值爲2？ –

最後兩行遵循對數的基本規則。請通過汗學院教程進行基本的對數概念。 –

爲了找出對的n，8n^2和64nlogn其值具有相同的值：

8n2 < 64nlogn 
8n.n < 8n.8.logn 
n < 8.logn 
n/8 < logn

我們知道m = logaX因此a^m = x，因此

2^n/8 < n

的算法分析，做基2，a = 2。在Python解決這個問題：

n = 2 
while 2 ** (n/8.0) < n: 
    n +=1 
print("Maximum value of n for which insertion sort beats merge sort is", n - 1)

這個參考幫助和其他測驗：

來源

2018-01-15 03:17:52 Brayoni

插入排序擊敗歸併排序N <= 8logn，正

回答

相關問題