計算函數的空間複雜度和時間複雜度

-2

作爲課程工作的一部分，我需要計算程序的複雜性。我想計算下面程序的空間複雜度和時間複雜度，我該如何計算它？如果有人能詳細解釋它，對我來說真的很有幫助。計算函數的空間複雜度和時間複雜度

sub find_multi_string { 
    my ($file, @strings) = @_; 
    my $fh; 
    open ($fh, "<$file"); 
    #store the whole file in an array 
    my @array = <$fh>; 

    for my $string (@strings) { 
     if (grep /$string/, @array) { 
      next; 
     } else { 
      die "Cannot find $string in $file"; 
     } 
    } 

    return 1; 
}

來源

2014-07-08 user3773222

人們不會回答這個問題，因爲他們要麼過於專注於這個問題，沒有對發生的事情有概念性的理解，要麼從基礎開始，這在很多地方已經很好地解釋了，包括在線（並且大概在你的課程筆記和講座中）。這絕對是其中值得找到一些好的參考資料，並投入時間來正確理解它的其中一件事。 –

空間複雜性：識別「大量」或「重複」出現的數據。爲這些數量指定數字，例如，N =文件中的行數，或M =數組中的元素數量。添加這些數量。注意動態創建數據結構：如果您有一組N個數字和另一個M數字，並且創建了所有產品的表格，則表格的空間複雜度爲...

時間複雜性：識別重複的行爲。有些可能是隱藏的（如在Perl中），有些是明確的，例如，在for循環中。使用空間複雜度的結果來量化這些重複。循環可能會提前終止：那麼您必須估計執行的平均時間。一個接一個地發生的循環加起來。如果你知道一個循環體被執行了N次，並且這個主體包含一個執行了M次的內部循環，那麼這個內部循環的主體會被執行 - 多久？

很多時候，這只是一個簡單的計算，簿記和簡單算術運算，儘管有好幾個例子，好的答案需要重數學。

不在你的情況！

來源

2014-07-08 18:02:34 laune

感謝您的解釋 – user3773222

嗯 - 你可以關閉問題/接受答案嗎？如果不是，爲什麼？ – laune

計算函數的空間複雜度和時間複雜度

回答

相關問題