編輯-這個問題來自我課程中的前一個測驗，官方答案是 O(n)
我需要幫助理解為什么以下代碼中的運行時復雜性是O(n)而不是O(n*log(n))
def fun(n):
total = 0
while n > 5:
n = n // 2
total = sum(range(n))
return total
while回圈執行log(n)時間，并在每次迭代中求和函式的款項n/2，因此號碼，它的復雜性o(n)，我看到每個while迭代有較少的號碼總和，但我不明白為什么它的O(n)。
謝謝你。
uj5u.com熱心網友回復：
所以我想通了。
每次while迭代對n/2專案求和。這意味著總迭代次數是n\2 n\4 n\8 ...，并且這個總和收斂到n
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/406820.html
標籤：
下一篇：原生函式是什么意思？
IEEE1588ptp在數字化變電站時鐘同步方面的應用 京準電子科技官微——ahjzsz 一、電力系統時間同步基本概況 隨著對IEC 61850標準研究的不斷深入，國內外學者提出基于IEC61850通信標準體系建設數字化變電站的發展思路。數字化變電站與常規變電站的顯著區別在于程序層傳統的電流/電壓互 ......
uj5u.com 2020-09-10 03:51:52 moreCL.TE 簡介 前端通過Content-Length處理請求，通過反向代理或者負載均衡將請求轉發到后端，后端Transfer-Encoding優先級較高，以TE處理請求造成安全問題。 檢測 發送如下資料包 POST / HTTP/1.1 Host: ac391f7e1e9af821806e890 ......
uj5u.com 2020-09-10 03:52:11 more網路滲透資料大全單——漏洞庫篇漏洞庫 NVD ——美國國家漏洞庫 →http://nvd.nist.gov/。 CERT ——美國國家應急回應中心 →https://www.us-cert.gov/ OSVDB ——開源漏洞庫 →http://osvdb.org Bugtraq ——賽門鐵克 →ht ......
uj5u.com 2020-09-10 03:52:15 more京準講述NTP時鐘服務器應用及原理京準講述NTP時鐘服務器應用及原理 安徽京準電子科技官微——ahjzsz 北斗授時原理 授時是指接識訓通過某種方式獲得本地時間與北斗標準時間的鐘差，然后調整本地時鐘使時差控制在一定的精度范圍內。 衛星導航系統通常由三部分組成：導航授時衛星、地面檢測校正維護系統和用戶 ......
uj5u.com 2020-09-10 03:52:25 more利用北斗衛星系統設計NTP網路時間服務器 利用北斗衛星系統設計NTP網路時間服務器 安徽京準電子科技官微——ahjzsz 概述 NTP網路時間服務器是一款支持NTP和SNTP網路時間同步協議，高精度、大容量、高品質的高科技時鐘產品。 NTP網路時間服務器設備采用冗余架構設計，高精度時鐘直接來源于北斗 ......
uj5u.com 2020-09-10 03:52:35 more詳細解讀電力系統各種對時方式 詳細解讀電力系統各種對時方式 安徽京準電子科技官微——ahjzsz，更多資料請添加VX 衛星同步時鐘是我京準公司開發研制的應用衛星授時時技術的標準時間顯示和發送的裝置，該裝置以M國全球定位系統（GLOBAL POSITIONING SYSTEM,縮寫為GPS）或者我國北 ......
uj5u.com 2020-09-10 03:52:45 more不管企業規模的大小，只要企業想省錢，那么企業的某些服務就一定會采用外包的形式，然而看似美好又經濟的策略，其實也有不好的一面。下面我通過安全的角度來聊聊使用外包團的安全隱患問題。 先看看什么服務會使用外包的，最常見的就是話務/客服這種需要大量重復性、無技術性的服務，或者是一些銷售外包、特殊的職能外包等 ......
uj5u.com 2020-09-10 03:52:57 more0x01 什么是SQL注入 SQL是一種注入攻擊，通過前端帶入后端資料庫進行惡意的SQL陳述句查詢。 0x02 SQL整型注入原理 SQL注入一般發生在動態網站URL地址里，當然也會發生在其它地發，如登錄框等等也會存在注入，只要是和資料庫打交道的地方都有可能存在。 如這里http://192.168. ......
uj5u.com 2020-09-10 03:55:40 moregit泄露獲取原始碼 使用GET傳參，引數為exp 經過三層過濾執行 第一層過濾偽協議，第二層過濾帶引數的函式，第三層過濾一些函式 preg_replace('/[a-z,_]+\((?R)?\)/', NULL, $_GET['exp'] (?R)參考當前正則運算式，相當于匹配函式里的引數 因此傳遞 ......
uj5u.com 2020-09-10 03:56:07 more在前面的Blog例子中我們使用的是GraphQL, 雖然GraphQL的使用處于上升趨勢,但是Rest API還是使用的更廣泛一些. 所以還是決定回到傳統的rest api framework上來, Django rest framework的官網上給了一個很好用的QuickStart, 我參考Qu ......
uj5u.com 2023-04-20 08:17:54 more這里給大家分享我在網上總結出來的一些知識，希望對大家有所幫助 大家平時在開發的時候有沒被new Date()折磨過？就是它的諸多怪異的設定讓你每每用的時候，都可能不小心踩坑。造成程式意外出錯，卻一下子找不到問題出處，那叫一個煩透了…… 下面，我就列舉它的“四宗罪”及應用思考 可惡的四宗罪 1. Sa ......
uj5u.com 2023-04-20 08:17:47 more實作文字跑馬燈效果，首先用到 substring()截取 和 setInterval計時器 clearInterval()清除計時器 效果如下： 實作代碼如下： <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta ......
uj5u.com 2023-04-20 08:12:31 moreJavaScript 運算子/運算子 在 JavaScript 中，有一些運算子可以使代碼更簡潔、易讀和高效。以下是一些常見的運算子： 1、可選鏈運算子（optional chaining operator） ?.是可選鏈運算子（optional chaining operator）。?. 可選鏈操 ......
uj5u.com 2023-04-20 08:02:25 more一、概述 rem是一個相對長度單位，它的單位長度取決于根標簽html的字體尺寸。rem即root em的意思，中文翻譯為根em。瀏覽器的文本尺寸一般默認為16px，即默認情況下： 1rem = 16px rem布局原理：根據CSS媒體查詢功能，更改根標簽的字體尺寸，實作rem單位隨螢屏尺寸的變化，如 ......
uj5u.com 2023-04-20 08:02:21 more好家伙,我的包終于開發完啦 歡迎使用胖虎的飛機大戰包!! 為你的主頁添加色彩 這是一個有趣的網頁小游戲包,使用canvas和js開發 使用ES6模塊化開發 效果圖如下: (覺得圖片太sb的可以自己改) 代碼已開源!! Git: https://gitee.com/tang-and-han-dynas ......
uj5u.com 2023-04-20 08:01:50 more我們都知道,通常情況下我們使用 vue 大多都是用的 SFC(Signle File Component)單檔案組件模式,即一個組件就是一個檔案,但其實 Vue 也是支持使用 JSX 來撰寫組件的。這里不討論 SFC 和 JSX 的好壞,這個仁者見仁智者見智。本篇文章旨在帶領大家快速了解和使用 Vu ......
uj5u.com 2023-04-20 08:01:37 more本章目標：計算屬性是如何實作的？計算屬性快取原理以及洋蔥模型的應用？在初始化Vue實體時，我們會給每個計算屬性都創建一個對應watcher，我們稱之為計算屬性watcher ......
uj5u.com 2023-04-20 08:01:31 more一、http是什么 通俗來講，http就是計算機通過網路進行通信的規則，是一個基于請求與回應，無狀態的，應用層協議。常用于TCP/IP協議傳輸資料。目前任何終端之間任何一種通信方式都必須按Http協議進行，否則無法連接。tcp(三次握手，四次揮手)。 請求與回應：客戶端請求、服務端回應資料。 無狀態 ......
uj5u.com 2023-04-20 08:01:10 more一、http是什么 通俗來講，http就是計算機通過網路進行通信的規則，是一個基于請求與回應，無狀態的，應用層協議。常用于TCP/IP協議傳輸資料。目前任何終端之間任何一種通信方式都必須按Http協議進行，否則無法連接。tcp(三次握手，四次揮手)。 請求與回應：客戶端請求、服務端回應資料。 無狀態 ......
uj5u.com 2023-04-20 08:00:32 more