ck1090758@gl.ck.tp.edu.tw
(peienwu)
學校
:
臺北市立建國高級中學
編號 : 128355
來源 : [27.247.166.72]
最後登入時間 ：
2021-10-16 11:22:04
jason.program.cpp@gmail.com
(資訊先生)
學校
:
不指定學校
編號 : 238091
來源 : [111.250.64.212]
最後登入時間 ：
2024-07-04 19:31:05
jason.program.cpp@gmail.com
(資訊先生)
學校
:
不指定學校
編號 : 238091
來源 : [111.250.64.212]
最後登入時間 ：
2024-07-04 19:31:05
如題，使用O(n^2)爆搜也會過
也有O(n)的算法，就是區間最大連續和
可以不用O(n^2)，使用邏輯判斷可以推導出 左位置，必小於 右位置 => 只需要O( ((n+1)n)/2 )
(身為一位高中生，因該知道這種邏輯)
搜尋方法如下，A1 A2 A3 .......An
1."左值"設在位置1 ，遍歷後方所有的值，當作"右值"。
2."左值"設在位置2 ，遍歷後方所有的值，當作"右值"。
3.以此類推直到"左值"設在位置n，停止搜尋。
ps:"左值": 為要撿起的連續 蘑菇中 最初撿起的那一個
"右值": 為要撿起的連續 蘑菇 中 最後撿起的那一個
jason.program.cpp@gmail.com
(資訊先生)
學校
:
不指定學校
編號 : 238091
來源 : [111.250.64.212]
最後登入時間 ：
2024-07-04 19:31:05
如題，使用O(n^2)爆搜也會過
也有O(n)的算法，就是區間最大連續和
可以不用O(n^2)，使用邏輯判斷可以推導出 左位置，必小於 右位置 => 只需要O( ((n+1)n)/2 )
(身為一位高中生，因該知道這種邏輯)搜尋方法如下，A1 A2 A3 .......An
1."左值"設在位置1 ，遍歷後方所有的值，當作"右值"。2."左值"設在位置2 ，遍歷後方所有的值，當作"右值"。
3.以此類推直到"左值"設在位置n，停止搜尋。
ps:"左值": 為要撿起的連續 蘑菇中 最初撿起的那一個
"右值": 為要撿起的連續 蘑菇 中 最後撿起的那一個
所以，時間複雜度為: O((n-0)+(n-1)+(n-2)+(n-3)+......+(2)+(1))，可得:O((n+1)n/2)
liaoweichen1024@gmail.com
(M_SQRT)
學校
:
新北市立新莊高級中學
編號 : 195452
來源 : [122.116.111.175]
最後登入時間 ：
2024-11-10 18:46:03
如題，使用O(n^2)爆搜也會過
也有O(n)的算法，就是區間最大連續和
可以不用O(n^2)，使用邏輯判斷可以推導出 左位置，必小於 右位置 => 只需要O( ((n+1)n)/2 )
(身為一位高中生，因該知道這種邏輯)搜尋方法如下，A1 A2 A3 .......An
1."左值"設在位置1 ，遍歷後方所有的值，當作"右值"。2."左值"設在位置2 ，遍歷後方所有的值，當作"右值"。
3.以此類推直到"左值"設在位置n，停止搜尋。
ps:"左值": 為要撿起的連續 蘑菇中 最初撿起的那一個
"右值": 為要撿起的連續 蘑菇 中 最後撿起的那一個
所以，時間複雜度為: O((n-0)+(n-1)+(n-2)+(n-3)+......+(2)+(1))，可得:O((n+1)n/2)
這就是 $O(N^2)$ 喔！