所以我最近開始研究資料結構和演算法，特別是大 O 表示法。到目前為止，我已經掌握了基礎知識。作為一個練習，我想確定我不久前撰寫的演算法的時間復雜度。
我的程式使用 PIL 或枕頭制作聯系表。基本上是self.imageCount大量影像的拼貼畫。我花了很多時間思考如何有效地計算每個影像的大小，以便將它們全部放在作業表上。
最后我想出了這個
我會讓函式自己說話。
def calc_size(self):
"""
Calculates size of each image by stating with a maximum height, then slowly
decreasing it until enough rows and columns can be formed to fit all images.
"""
self.height = self.sheetHeight
self.width = self.height * (2/3) # The aspect ratio is located here
self.rows, self.cols = 1, 1
while self.rows * self.cols < self.imageCount:
self.height -= 1
self.width = int(self.height * (2/3))
self.rows = self.calc_rows()
self.cols = self.calc_cols()
"""
The two functions below simply prevent zero division later in the program
when I calculate the gap between each image
"""
def calc_rows(self):
if int(self.sHeight/self.height) == 0:
return 1
return int(self.sHeight/self.height)
def calc_cols(self):
if int(self.sWidth/self.width) == 0:
return 2
return int(self.sWidth/self.width)
所以我的問題是，時間復雜度是calc_size多少？我已經運行了一些測驗，我推self.imageCount到了 10 000 并且運行時間從未真正超過 0.004 秒。這讓我認為它是 O(log n)。但是為什么……我不知道。
uj5u.com熱心網友回復：
假設紙張的縱橫比和影像的縱橫比相等，答案將是 O(· sheetHeight)。
讓我們考慮最壞的情況。讓我們暫時假設imageCount它非常大，以至于影像必須縮小到一個像素。然后，while 回圈的執行次數將等于self.sheetHeight - 1。因此，函式將是 O( sheetHeight)。
在您的情況下，縱橫比似乎相等，但假設它們不相等，那么答案是 O( sheetHeight) 或 O( sheetWidth) 之一。例如，影像寬度是影像高度的 1/2。由于 2/3 > 1/2，限制方向是高度（高度將首先達到限制）。那么答案就是 O(· sheetHeight)。
編輯：對于大 O 而言imageCount，請考慮以下事項：
為簡單起見，我假設作業表和影像的縱橫比相同。
讓我們imageHeight成為影像所需的高度。說imageCount = 100。然后imageHeight=sheetHeight/10。
現在，假設我們乘以imageCount4。現在imageHeight必須是sheetHeight/20。因此，我們可以看到影像高度與 成正比1/sqrt(imageCount)。
但是，時間復雜度實際上取決于sheetHeight - imageHeight執行 while 回圈的次數。因此，我們可以說解是 O( sheetHeight - imageHeight) = O( sheetHeight - sheetHeight/sqrt(imageCount)) = O( 1 - 1/sqrt(imageCount)) （假設sheetHeight是常數）。
因此，如果我們取n = imageCount，則解決方案是 O( 1-1/sqrt(n))。這解釋了為什么對于大影像計數，解決方案接近恒定的時間消耗。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/418818.html
標籤：