O、Θ、Ω、o、ω,別再傻傻分不清了!

来源:https://www.cnblogs.com/tong-yuan/archive/2020/07/23/13369488.html

前言 本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。 你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。 前面幾節,我們一起學習了演算法的複雜度如何分析,並從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了演算法的複雜度,在我們表示覆雜度的 ...


file

前言

本篇文章收錄於專輯:http://dwz.win/HjK,點擊解鎖更多數據結構與演算法的知識。

你好,我是彤哥,一個每天爬二十六層樓還不忘讀源碼的硬核男人。

前面幾節,我們一起學習了演算法的複雜度如何分析,並從最壞、平均、最好以及不能使用最壞情況全方位無死角的剖析了演算法的複雜度,在我們表示覆雜度的時候,通常使用大O來表示。

但是,在其他書籍中,你可能還見過Θ、Ω、o、ω等符號。

那麼,這些符號又是什麼意思呢?

本節,我們就來解決這個問題。

讀音

我們先來糾正一波讀音:

  • O,/əʊ/,大Oh
  • o,/əʊ/,小oh
  • Θ,/ˈθiːtə/,theta
  • Ω,/oʊˈmeɡə/,大Omega
  • ω,/oʊˈmeɡə/,小omega

是不是跟老師教得不太一樣^^

數學解釋

Θ

Θ定義了一種精確的漸近行為(exact asymptotic behavior),怎麼說呢?

用函數來表示:

對於f(n),存在正數n0、c1、c2,使得當 n>=n0 時,始終存在 0 <= c1*g(n) <= f(n) <= c2*g(n),則我們可以用 f(n)=Θ(g(n))表示。

用圖來表示:

file

Θ同時定義了上界和下界,f(n)位於上界和下界之間,且包含等號。

比如說,f(n) = 2n^2+3n+1 = Θ(n^2),此時,g(n)就是用f(n)去掉低階項和常數項得來的,因為肯定存在某個正數n0、c1、c2,使得 0 <= c1*n^2 <= 2n^2+3n+1 <= c2*n2,當然,你說g(n)是2*n2也沒問題,所以,g(n)實際上滿足這個條件的一組函數。

好了,如果Θ你能理解了,下麵四個就好理解了。

O

O定義了演算法的上界。

用函數來表示:

對於f(n),存在正數n0、c,使得當 n>=n0 時,始終存在 0 <= f(n) <= c*g(n),則我們可以用 f(n)=O(g(n))表示。

用圖來表示:

file

O只定義上界,只要f(n)不大於c*g(n),就可以說 f(n)=O(g(n))。

比如說,對於插入排序,我們說它的時間複雜度是O(n^2),但是,如果用Θ來表示,則必須分成兩條:

  1. 最壞的情況下,它的時間複雜度為Θ(n^2);
  2. 最好的情況下,它的時間複雜度為Θ(n)。

這裡的n2只是g(n)這一組函數中最小的上界,當然,g(n)也可以等於n3。

不過,我們一般說複雜度都是指的最小的上界,比如,這裡插入排序的時間複雜度如果說是O(n^3),從理論上來說,也沒問題,只是不符合約定罷了。

插入排序最好的情況就是數組本身就是有序的。

o

o定義的也是演算法的上界,不過它不包含等於,是一種不精確的上界,或者稱作松上界(某些書籍翻譯為非緊上界)。

用函數來表示:

對於f(n),存在正數n0、c,使得當 n>n0 時,始終存在 0 <= f(n) < c*g(n),則我們可以用 f(n)=o(g(n))表示。

用圖來表示:

file

o表示僅僅是大O去掉等於的情況,其他行為與大O一模一樣。

Ω

Ω定義了演算法的下界,與O正好相反。

用函數來表示:

對於f(n),存在正數n0、c,使得當 n>=n0 時,始終存在 0 <= c*g(n) <= f(n),則我們可以用 f(n)=Ω(g(n))表示。

用圖來表示:

file

Ω只定義下界,只要f(n)不小於c*g(n),就可以說 f(n)=Ω(g(n))。

比如,對於插入排序,我們可以說它的時間複雜度為Ω(n),不過,這通常沒有什麼意義,因為插入排序在最好的情況下很少,基本都是在最壞情況或者平均情況。

ω

ω同樣定義的是下界,只不過不包含等於,是一種不精確的下界,或者稱作松下界(某些書籍翻譯為非緊下界)。

用函數來表示:

對於f(n),存在正數n0、c,使得當 n>n0 時,始終存在 0 <= c*g(n) < f(n),則我們可以用 f(n)=ω(g(n))表示。

用圖來表示:

file

ω表示僅僅是大Ω去掉等於的情況,其他行為與大Ω一模一樣。

通俗理解

符號 含義 通俗理解
Θ 精確的漸近行為 相當於“=”
O 上界 相當於“<=”
o 松上界 相當於“<”
Ω 下界 相當於“>=”
ω 松下界 相當於“>”

小結

為了幫助同學們快速查閱英文資料,彤哥特地把這幾節涉及到的英語單辭彙總了一下:

漢語 英文
複雜度 complexity
時間複雜度 time complexity
空間複雜度 space complexity
漸近分析 asymptotic analysis
最壞情況 the worst case
最好情況 the best case
平均情況 the average case
精確的漸近行為 exact asymptotic behavior
低階項 low order terms
常數項(前置常數) leading constants
松上界 loose upper-bound

後記

本節,我們分別從讀音、數學、通俗理解等三個方面闡述了Θ、O、o、Ω、ω的含義,併在最後給出了這幾節涉及到的術語對應的英文,有了這些英文,你也可以快速地查閱這方面的資料。

不過,在我們平時與人交流的過程中,大家還是習慣於使用大O表示法,一來它表示最壞情況,最壞情況通常可以直接代表演算法的複雜度,二來它比較好書寫。

所以,我們只需要記住大O就可以了,只不過在別人提到Θ、Ω、ω我們知道是什麼含義就可以了。

前面幾節講了這麼多,其實,還是只涉及了很簡單的演算法複雜度。

那麼,常見的演算法複雜度有哪些呢?

下一節,我們接著聊。

關註公號主“彤哥讀源碼”,解鎖更多源碼、基礎、架構知識。


您的分享是我們最大的動力!

更多相關文章
  • BOM(瀏覽器對象模型)簡介、window對象、location對象、history對象、navigator對象、screen對象、document對象 ...
  • 效果圖看左上角 代碼如下: <!DOCTYPE html> <html> <head> <meta charset="UTF-8"> <title>基於CSS3的3D立方體旋轉動畫</title> <style> /* 3d旋轉樣式 */ .cub { width: 2.5rem; height: ...
  • 最近工作中用到了jQuery UI中排序和拖拽功能,花了大概一天的時間,搞清楚了大概的參數配置,以及遇到的一些問題,總結如下。 sortable 簡單的配置如下: $('#subs-box').sortable({ axis: 'y', cursor: 'ns-resize', placeholde ...
  • 室內地圖製作經過易景空間地圖團隊的持續優化迭代,新版本地圖編輯器中的畫圓柱體、模型庫、快速畫道路、房間直接換紋理貼圖等功能終於上線了,目前市面上一款無需安裝軟體就能直接使用瀏覽器訪問的線上室內地圖製作編輯器。 ...
  • 摘要 重裝電腦系統後,使用npm install初始化項目依賴失敗了,錯誤提示:'proxy' config is set properly..........,具體的錯誤提示如下圖所示: 解決方案 經過報錯信息查詢解決辦法,最終找到了兩個比較好的方案,在此總結一下,以便下次再遇到此類問題。 方案一 ...
  • 引入Javascript的發展史 JavaScript的基本語法篇 1.與HTML結合的方式 2.0 註釋與數據類型 3.0 變數 4.0 運算符 (1)一元運算符 (2)比較運算符 (3)邏輯運算符 (4)三元運算符 5.流程式控制制語句 6.JS特殊語法 練習:在頁面上列印一個99乘法表 <!DOC ...
  • 隨著我國經濟的飛速發展,三維地下管網、地下管線系統直觀高效的參考,結合GIS、資料庫和三維技術,直觀顯示地下管線的空間層次和位置信息,資源的統籌利用審批工作提供準確,易景空間地圖專業致力於三維管網、管網建模、bim管線、三維管網檢測提供專業的技術服務,數據驅動快速生成三維管網矢量模型。 ...
  • 一,效果圖。 二,代碼。 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title>CSS 偽類</title> <style> a:link { color: #FF0000; } /* unvisited link */ a:visi ...
一周排行
  • 比如要拆分“呵呵呵90909086676喝喝999”,下麵當type=0返回的是中文字元串“呵呵呵,喝喝”,type=1返回的是數字字元串“90909086676,999”, private string GetStrings(string str,int type=0) { IList<strin ...
  • Swagger一個優秀的Api介面文檔生成工具。Swagger可以可以動態生成Api介面文檔,有效的降低前後端人員關於Api介面的溝通成本,促進項目高效開發。 1、使用NuGet安裝最新的包:Swashbuckle.AspNetCore。 2、編輯項目文件(NetCoreTemplate.Web.c ...
  • 2020 年 7 月 30 日, 由.NET基金會和微軟 將舉辦一個線上和為期一天的活動,包括 微軟 .NET 團隊的演講者以及社區的演講者。本次線上大會 專註.NET框架構建微服務,演講者分享構建和部署雲原生應用程式的最佳實踐、模式、提示和技巧。有關更多信息和隨時瞭解情況:https://focu... ...
  • #abp框架Excel導出——基於vue #1.技術棧 ##1.1 前端採用vue,官方提供 UI套件用的是iview ##1.2 後臺是abp——aspnetboilerplate 即abp v1,https://github.com/aspnetboilerplate/aspnetboilerp ...
  • 前言 本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。 作者:碧茂大數據 PS:如有需要Python學習資料的小伙伴可以加下方的群去找免費管理員領取 input()輸入 Python提供了 input() 內置函數從標準輸入讀入一 ...
  • 從12年到20年,python以肉眼可見的趨勢超過了java,成為了當今It界人人皆知的編程語言。 python為什麼這麼火? 網路編程語言搜索指數 適合初學者 Python具有語法簡單、語句清晰的特點,這就讓初學者在學習階段可以把精力集中在編程對象和思維方法上。 大佬都在用 Google,YouT ...
  • 在社會上存在一種普遍的對培訓機構的學生一種歧視的現象,具體表現在,比如:當你去公司面試的時候,一旦你說了你是培訓機構出來的,那麼基本上你就涼了,那麼你瞞著不說,然後又通過了面試成功入職,但是以後一旦在公司被髮現有培訓經歷,可能會面臨被降薪,甚至被辭退,培訓機構出來的學生,在用人單位眼裡就是能力低下的 ...
  • from typing import List# 這道題看了大佬寫的代碼,經過自己的理解寫出來了。# 從最外圍的四周找有沒有為O的,如果有的話就進入深搜函數,然後深搜遍歷# 判斷上下左右的位置是否為Oclass Solution: def solve(self, board: List[List[s ...
  • import requests; import re; import os; # 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537.36 (KHTML, li ...
  • import requests; import re; import os; import parsel; 1.請求網頁 header = { "user-agent":'Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_5) AppleWebKit/537. ...