已解決430363個問題，去搜搜看，總會有你想問的

bigO，你如何計算/近似它？

首頁猿問 bigO，你如何計算/近似它？

Java 算法與數據結構

慕蓋茨4494581 2019-05-24 15:07:27

bigO，你如何計算/近似它？大多數擁有CS學位的人肯定會知道Big O代表什么。它可以幫助我們衡量算法的實際效率（如何），如果你知道你試圖解決的問題屬于哪個類別，你可以弄清楚是否仍然可以擠出那么少的額外性能。1但我很好奇，你如何計算或近似算法的復雜性？

查看完整描述

3 回答

肥皂起泡泡

TA貢獻1829條經驗獲得超6個贊

小提示：big O符號用于表示漸近復雜度（即，當問題的大小增長到無窮大時），并且它隱藏了一個常量。

這意味著在O（n）中的算法和O（n ²）中的算法之間，最快的并不總是第一個（盡管總是存在n的值，使得對于大小> n的問題，第一個算法是最快的）。

請注意，隱藏常量很大程度上取決于實現！

此外，在某些情況下，運行時不是輸入大小 n的確定性函數。例如，使用快速排序進行排序：對n個元素的數組進行排序所需的時間不是常量，而是取決于數組的起始配置。

有不同的時間復雜性：

一個很好的介紹是R. Sedgewick和P. Flajolet 的算法分析導論。

正如您所說，premature optimisation is the root of all evil并且（如果可能的話）在優化代碼時應始終使用分析。它甚至可以幫助您確定算法的復雜性。

反對回復 2019-05-24

關注

舉報

0/150

提交

取消