想請問直譯式的程式中能夠直接計算程式複雜度,目前正已物件導向的方式開始在寫程式,途中想到一個問題如題:
1.有甚麼方法可以計算物件導向中的時間複雜度??
2.應該針對每個class中的函式個別計算嗎?
補上範例:
A.php
namespace C01;
class hello{
public function() hello{
return '1';
}
}
B.php
namespace C02;
class hello{
public function() hello{
return '2';
}
}
c.php
class Loader {
public function load($ns, $cls) {
return $this->loadFile($ns, $cls);
}
private function loadFile($ns, $cls) {
require_once "$ns/$cls.php";
$classname = "\\$ns\\$cls";
return new $classname();
}
}
如題透過C.php呼叫其他檔案中的物件,想知道這樣的效率或是應該說時間複雜度應該怎麼計算?
或是應該透過其他方法去了解這樣的寫法是否能夠更精簡
ps:懇請解惑~謝謝各位大大
已邀請的邦友 {{ invite_list.length }}/5
依據這篇的教學
如果我沒算錯
A.php B.php C.php 的時間複雜度
都是 O(1)
看完後不知道我理解正不正確~ 想知道時間複雜度,我應該將物件的function單獨來看以及使用的方式,所以上面的例子都是O(1),倘若有迴圈的function則必須是O(n)....等之類的,以此類推
O(n)不代表表執行時間，它代表的是執行時間隨著數據規模增長的變化趨勢
你的程式
執行時間隨著數據規模的變化趨勢是一水平線
(也就是不管數據再多再少執行時間都沒什麼變化)
所以是 O(1)
了解了~~謝謝海綿大大
今天剛好測試了一下費氏數列，遞迴解的時間複雜度是O(2^n)，用node.js、python、php各寫一個來比較，fib(100)跑的時間各別是1.6秒、56秒、22秒....改成迴圈（O(n)）就都變成0秒。
今天剛好測試了一下費氏數列...
有此閒情雅緻
敢情費大公已經在等過年了
回頭看一下，是fib(40)
function call(or context switch)發生331160281次...
結論：node.js的user land function執行的成本可能比較低
這週工作是寫refactoring的規劃...剛好有老舊東西要從python轉到其他平台。
對於fillano大的測試很感興趣,題外話:高併發的需求效能是不是 node.js >php ?
每個語言都有他適合的場景。
話說這次也測到一個問題，node.js跑到超過fib(78)後，會跟php與python跑出來的結果不一樣了，懷疑是node.js的問題。
阿，超過fib(78)後，會超過node.js整數所能表示的最大值(2^53)，這時要改用Bigint才能跑出正確結果。然後跑fib(10000)的話，python花了0.007秒，node.js花了0.013秒，python勝出。沒有php的結果，因為超過他能計算的範圍了。
謝謝大大的測試~這樣的測試還真的沒有想過呢又學了一些新知識~
如果把計算方法改成尾遞迴（tail recursion）的形式，還有可能進一步提升遞迴解法的速度。原本的寫法是：
let count = 0;
let input = 40n;
function fibonacci(i) {
count++;
if(i < 2n) {
return i;
} else {
return fibonacci(i-1n) + fibonacci(i-2n);
}
}
let start = new Date().getTime();
console.log(fibonacci(input), (new Date().getTime() - start) / 1000, count);
這樣因為呼叫兩次fibonacci()，不是尾遞迴。改成尾遞迴的作法其實想法類似迴圈（for(let n=input, a=0, b=1; n>=0; n--) {...}）：
let count = 0;
let input = 40n;
function fibonacci(n, a = 0n, b = 1n) {
count++;
if (n == 0n){
return a;
}
if (n == 1n){
return b;
}
return fibonacci(n - 1n, b, a + b);
}
let start = new Date().getTime();
console.log(fibonacci(input), (new Date().getTime() - start) / 1000, count);
這樣可以讓複雜度變成O(n)。缺點是，因為函數呼叫有overhead，所以存在遞迴呼叫的限制，而真的用迴圈的話就沒這個問題。
改用BigInt算，會發現效能變差（fib(40)從1.6秒變成34秒），可能BigInt還是實驗性規格，所以沒最佳化...結果最佳的做法是用python+迴圈來算fibonacci。
再次感恩大大的測試~小的我服用了
iThome鐵人賽
看影片追技術