Re: [閒聊] 每日LeetCode
※ 引述《oin1104 (是oin的說)》之銘言：
: 原本想自己先試試看
: 直接暴力拆開來解
: 結果runtime error
你做的大概是對的
不過問題就在演算法
這也是你以後才會學到的
這邊我們先做一些簡化
大概理解一下演算法在幹什麼就好
我們假定你的每一行程式它要花的時間就是1
那下面這個
for(int i = 0; i < 10; i++) {
myVar++;
myVar--;
}
我們就能知道它做了10次myVar++以及10次myVar--
然後可能還有給for用的i = 0, i++以及i < 10
這樣就是花了20(myVar) + 21(for) = 41的時間
演算法的目的就是去推算你的程式花了多少時間、以及多少空間(記憶體)
在我們要處裡的資料很大的時候
例如一萬筆 或是一億筆
那那些基本的操作影響就會變得很小
例如int i = 0
演算法中對程式造成大量影響就是你的迴圈怎麼用
你原本的算法長這樣
for(distSize)
while(1)
{
for(distSize)
for(distSize)
for(distSize)
}
這個時間複雜就是10^5 + 10^5 * (10^5*3)
造成最大的影響就是10^5*10^5
後來換成新的
for(distSize)
while(1)
時間複雜度是10^5*2
二十萬跟三百億比起來就差很多
這就是你超時的主要原因
從上面的算式比下來
我們就能知道
演算法中單行程式我們都會無視
然後倍數的差距其實也是很小的
(跑一次迴圈十萬跟跑兩次迴圈二十萬比)
會影響最大的是你用了幾層巢狀迴圈
(單迴圈十萬跟跟巢狀迴圈一百億)
所以能避免巢狀迴圈就盡量避免
當然比巢狀迴圈更可怕的就別說了
當然上面說的演算法程式都是不包含IO的
如果你要撈資料庫、撈後端資料、讀檔案之類的一行就有大量消耗
--
Zoosewu
Yoututbe顯示PTT推文
可以在各個網站追實況或Live時使用
預覽圖: https://i.imgur.com/ZhtXdAJ.png
完整介紹: https://github.com/zoosewu/PTTChatOnYoutube/tree/master/homepage
支援的網站: Youtube Twitch Holotools Niji-mado Holodex
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699357670.A.0F7.html
推
11/07 19:49,
2年前
, 1F
11/07 19:49, 1F
我的解題思路也會順便丟在leetcode
因為525害我們文章都會被吃掉
https://leetcode.com/Zoosewu/
登入之後點Solutions應該看的到(吧?)
然後會順便把複雜度放上去
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/07/2023 19:54:24
推
11/07 19:57,
2年前
, 2F
11/07 19:57, 2F
→
11/07 20:01,
2年前
, 3F
11/07 20:01, 3F
→
11/07 20:14,
2年前
, 4F
11/07 20:14, 4F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 497 之 719 篇)：