考慮算法複雜性分析的大上界

我在想算法的複雜性分析，我拿出這個例子：有一個醫療中心，有幾個醫生;每位醫生都可以在一週中的每個工作日的一小時內參觀。現在，假設我們有一組醫生，並且每位醫生都有一個預定訪問的排序集合，如果我們想要查找某個特定位置是否有任何醫生免費，我們可以編寫一個非常基本的算法來執行此操作：考慮算法複雜性分析的大上界

for (Doctor doc: doctors) { 
    for (Visit visit: doc.visits) { 
     if (visit.hour == hour && visit.day == day) { 
      return false; 
     } 
     if (visit.day > day) { 
      break; 
     } 
    } 
} 
return true;

雖然我知道這不是解決問題的最有效的方法，但我在想它的時間複雜性;在開始時我考慮了O（n^2）的時間複雜性，因爲醫生和訪問的數量可以增長，代碼包含兩個嵌套循環，而內部循環包含幾個常量操作。

但是後來我認爲醫生的數量肯定有一個上限，即生活在該中心國家的人數（如果我們考慮到即使是外國醫生，仍然有上限，世界人口〜7.5億美元）;所以時間複雜度似乎降低到線性O（n），因爲內部循環只執行一定數量的次數。在大-O項中：O（C * N）= O（n）其中C是恆定的上限。

不滿意，我還認爲這個軟件不會運行一個多世紀以來的醫療中心，因爲我相信在那段時間它會被重寫;所以軟件將只接受訪問，直到2117年，即假定每年230個工作日，每天8個插槽，184k個插槽，再次是上限。如果您認爲該軟件可以持續一個多世紀，那麼上限將成爲太陽（預計約50億年）的預期壽命，之後地球上的生命將會消失。更高的上限，但仍然是上限。所以現在的時間複雜度似乎是O（1），因爲O（C1 * C2）= O（1）其中C1是醫生上限，C2是訪問上限。

這個推理是否正確？在分析算法複雜性的同時，假設大數爲常量，通常是正確的？

來源

2017-04-22 Andrea Iacono

「假設n從不大於某個常數，f（n）的複雜性是多少」並不是一個有意義的問題。複雜性必然需要考慮任意大n的f（n）。 –

使用你的論點，你可能會認爲數組的快排是O（1），因爲世界上最大的計算機有（比如說）64TB ram，它限制了最大數組quicksort可以工作的大小。 –

@Paul Hankin：這正是我的想法。那麼，如果計算機結構本身是有限的（爲什麼有一個上限），爲什麼要談論漸近複雜？我錯過了什麼？ –

如果每個醫生有同等數量的visits，也就是說，如果下面的循環

for (Visit visit: doc.visits)

總是恆定的多次運行，那麼不要緊，無論它運行十億倍，或者運行10或20次。只要是恆定的數量，時間複雜度總是會爲O（n），其是直

原因是大O定義：

f(n) = O(g(n))當我們有f(n) <= cg(n)，所有n > n'和一些常數c。所以只要內循環運行一段時間，比如說次。我們有f(n) = 1000000n，我們得到：

f(n) = 1000000n <= 1000001n, for all n > 0 and c = 1000001

，我們得到F（N）= O（N）。

來源

2017-04-22 14:40:42

考慮算法複雜性分析的大上界

回答

相關問題