企业官网建设流程全解析

做淘宝网站需要多少钱,wordpress永久免费,一个电商网站的网页制作,曲周县建设局网站文章目录#x1f4d6; 问题描述#xff1a;一次买卖#xff0c;最大化利润#x1f9e0; 为什么不能用简单方法#xff1f;❌ 错误思路1#xff1a;贪心法#xff08;每次都选最便宜的买#xff0c;最贵的卖#xff09;❌ 错误思路2#xff1a;转化为最大子数组问题✅…文章目录 问题描述一次买卖最大化利润 为什么不能用简单方法❌ 错误思路1贪心法每次都选最便宜的买最贵的卖❌ 错误思路2转化为最大子数组问题✅ 正确思路分治法分治法的三个步骤1️⃣ **底Base Case**最简单的情况2️⃣ **分Divide**将问题一分为二3️⃣ **合Combine**合并子问题的解 算法伪代码 算法执行过程示例递归树自底向上合并过程 算法复杂度分析时间复杂度⚠️ 常见错误与注意事项错误2复杂度分析错误 核心要点总结 拓展思考 相关知识点 问题描述一次买卖最大化利润想象你开着一辆车从城市A到城市B沿途经过n个苹果市场编号1到n。在每个市场i你都知道买入价B[i]在这个市场买苹果的价格卖出价S[i]在这个市场卖苹果的价格约束条件车只能往前开不能往回开只能做一次买卖在一个市场买入在之后的市场卖出j ≥ i j \geq ij≥i目标找到最优的买入市场i和卖出市场j使得利润S [ j ] − B [ i ] S[j] - B[i]S[j]−B[i]最大如果无法盈利则最小化亏损。 为什么不能用简单方法❌ 错误思路1贪心法每次都选最便宜的买最贵的卖问题最便宜的买入点可能在最贵的卖出点之后违反了不能往回开的约束。❌ 错误思路2转化为最大子数组问题常见错误有些同学会联想到股票增值问题试图将问题转化为最大连续子数组问题。为什么不行股票问题中同一天的买入价和卖出价相同可以转化为价格差数组但本题中每个市场的买入价和卖出价不同不能简单转化例如市场4的买入价是2元卖出价是1元如果在这里买卖会亏损1元但我们可以在这里买入到其他市场卖出。✅ 正确思路分治法分治法的核心思想将大问题分解为小问题解决小问题再合并结果。分治法的三个步骤1️⃣底Base Case最简单的情况如果只有一个市场那么只能在这个市场买入并卖出利润 S [ i ] − B [ i ] S[i] - B[i]S[i]−B[i]2️⃣分Divide将问题一分为二将区间[ L , R ] [L, R][L,R]分成两个子区间左半部分[ L , Mid ] [L, \text{Mid}][L,Mid]右半部分[ Mid 1 , R ] [\text{Mid}1, R][Mid1,R]其中Mid ⌊ ( L R ) / 2 ⌋ \text{Mid} \lfloor (LR)/2 \rfloorMid⌊(LR)/2⌋⌊ ⌋ \lfloor \rfloor⌊⌋:指的是地板函数取下标。比如 当L0R5时(05)/22.5⌊2.5⌋23️⃣合Combine合并子问题的解最优解可能出现在三种情况中完全在左半部分在左子区间内买入和卖出完全在右半部分在右子区间内买入和卖出跨越中点在左半部分买入在右半部分卖出关键点对于跨越中点的情况最优策略是在左半部分选择最低的买入价B [ left ] B[\text{left}]B[left]在右半部分选择最高的卖出价S [ right ] S[\text{right}]S[right]利润 S [ right ] − B [ left ] S[\text{right}] - B[\text{left}]S[right]−B[left]最终答案从这三种情况中选择利润最大的。 算法伪代码算法DC-Max-Apple-Profit(B[], S[], L, R)输入买入价数组B[]卖出价数组S[]区间[L, R]输出最大利润M买入市场i卖出市场j1.ifLRthen// 底只有一个市场2. MS[L]- B[L]3. iL, jL4.return(M, i, j)5. endif6.else// 分将问题分解7. Mid⌊(LR)/2⌋8.(ML, IL, JL)DC-Max-Apple-Profit(B[], S[], L, Mid)// 左子问题9.(MR, IR, JR)DC-Max-Apple-Profit(B[], S[], Mid1, R)// 右子问题10.11. // 合合并子问题的解12. // 情况3跨越中点的情况13. B[left]min{B[u]|L ≤ u ≤ Mid}// 左半部分最低买入价14. S[right]max{S[u]|Mid1 ≤ u ≤ R}// 右半部分最高卖出价15. McS[right]- B[left]// 跨越中点的利润16.17. // 从三种情况中选择最优18.ifMcmax(ML, MR)then19. MMc, ileft, jright20.elseifMLMRthen21. MML, iIL, jJL22.else23. MMR, iIR, jJR24. endif25.26.return(M, i, j)27. endelse 算法执行过程示例让我们用示例数据演示算法执行过程递归树[1,6] / \ [1,3] [4,6] / \ / \ [1,2] [3,3] [4,5] [6,6] / \ / \ [1,1] [2,2] [4,4] [5,5]自底向上合并过程第1层叶子节点(底)[1,1]:M 3 − 5 − 2 M 3-5 -2M3−5−2[2,2]:M 3 − 4 − 1 M 3-4 -1M3−4−1[3,3]:M 7 − 8 − 1 M 7-8 -1M7−8−1[4,4]:M 1 − 2 − 1 M 1-2 -1M1−2−1[5,5]:M 6 − 7 − 1 M 6-7 -1M6−7−1[6,6]:M 7 − 9 − 2 M 7-9 -2M7−9−2第2层[1,2]:左子问题1,1:M − 2 M-2M−2右子问题(2,2):M − 1 M-1M−1跨越中点:min ⁡ ( B [ 1 ] , B [ 2 ] ) 4 \min(B[1],B[2])4min(B[1],B[2])4,max ⁡ ( S [ 2 ] ) 3 \max(S[2])3max(S[2])3,M c 3 − 4 − 1 M_c3-4-1Mc​3−4−1最优:M − 1 M-1M−1(右子问题或跨越中点)[4,5]:左子问题:M − 1 M-1M−1右子问题:M − 1 M-1M−1跨越中点:min ⁡ ( B [ 4 ] ) 2 \min(B[4])2min(B[4])2,max ⁡ ( S [ 5 ] ) 6 \max(S[5])6max(S[5])6,M c 6 − 2 4 M_c6-24Mc​6−24最优:M 4 M4M4(跨越中点)第3层[1,3]:左子问题[1,2]:M − 1 M-1M−1右子问题[3,3]:M − 1 M-1M−1跨越中点:min ⁡ ( B [ 1..2 ] ) 4 \min(B[1..2])4min(B[1..2])4,max ⁡ ( S [ 3 ] ) 7 \max(S[3])7max(S[3])7,M c 7 − 4 3 M_c7-43Mc​7−43最优:M 3 M3M3(跨越中点)[4,6]:左子问题[4,5]:M 4 M4M4右子问题[6,6]:M − 2 M-2M−2跨越中点:min ⁡ ( B [ 4..5 ] ) 2 \min(B[4..5])2min(B[4..5])2,max ⁡ ( S [ 6 ] ) 7 \max(S[6])7max(S[6])7,M c 7 − 2 5 M_c7-25Mc​7−25最优:M 5 M5M5(跨越中点)第4层根节点[1,6]:左子问题[1,3]:M 3 M3M3右子问题[4,6]:M 5 M5M5跨越中点:min ⁡ ( B [ 1..3 ] ) 4 \min(B[1..3])4min(B[1..3])4,max ⁡ ( S [ 4..6 ] ) 7 \max(S[4..6])7max(S[4..6])7,M c 7 − 4 3 M_c7-43Mc​7−43最优:M 5 M5M5(右子问题)买入市场4卖出市场6 算法复杂度分析时间复杂度递推关系T ( n ) 2 T ( n / 2 ) O ( n ) T(n) 2T(n/2) O(n)T(n)2T(n/2)O(n)求解过程每次递归将问题分成两个子问题每个子问题规模为n / 2 n/2n/2合并步骤需要O ( n ) O(n)O(n)时间找最小值和最大值根据主方法时间复杂度为O ( n log ⁡ n ) O(n \log n)O(nlogn)⚠️ 常见错误与注意事项错误2复杂度分析错误错误递推式T ( n ) 2 T ( n / 2 ) O ( 1 ) ❌ 错误 T(n) 2T(n/2) O(1) \quad \text{❌ 错误}T(n)2T(n/2)O(1)❌错误错误原因合并步骤需要处理跨越中点的情况必须重新扫描整个子区间在左半部分[ L , Mid ] [L, \text{Mid}][L,Mid]找最低买入价需要遍历左半部分的所有元素B [ left ] min ⁡ { B [ u ] ∣ L ≤ u ≤ Mid } B[\text{left}] \min\{B[u] \mid L \leq u \leq \text{Mid}\}B[left]min{B[u]∣L≤u≤Mid}左半部分规模Mid − L 1 ≈ n / 2 \text{Mid} - L 1 \approx n/2Mid−L1≈n/2时间复杂度O ( n / 2 ) O ( n ) O(n/2) O(n)O(n/2)O(n)在右半部分[ Mid 1 , R ] [\text{Mid}1, R][Mid1,R]找最高卖出价需要遍历右半部分的所有元素S [ right ] max ⁡ { S [ u ] ∣ Mid 1 ≤ u ≤ R } S[\text{right}] \max\{S[u] \mid \text{Mid}1 \leq u \leq R\}S[right]max{S[u]∣Mid1≤u≤R}右半部分规模R − ( Mid 1 ) 1 ≈ n / 2 R - (\text{Mid}1) 1 \approx n/2R−(Mid1)1≈n/2时间复杂度O ( n / 2 ) O ( n ) O(n/2) O(n)O(n/2)O(n)总时间O ( n / 2 ) O ( n / 2 ) O ( n ) O(n/2) O(n/2) O(n)O(n/2)O(n/2)O(n)为什么不能是O ( 1 ) O(1)O(1)需要扫描整个子区间才能确定最小值/最大值不能直接使用左右子问题的解因为跨越中点时的最优选择可能不是子问题的最优解例如左子问题可能在市场2买入4元但跨越中点时市场4的买入价2元更低应该选择市场4正确递推式T ( n ) 2 T ( n / 2 ) O ( n ) T(n) 2T(n/2) O(n)T(n)2T(n/2)O(n)复杂度求解使用主方法a 2 a 2a2,b 2 b 2b2,f ( n ) O ( n ) f(n) O(n)f(n)O(n)log ⁡ b ( a ) log ⁡ 2 ( 2 ) 1 \log_b(a) \log_2(2) 1logb​(a)log2​(2)1f ( n ) O ( n ) O ( n 1 ) O ( n log ⁡ b ( a ) ) f(n) O(n) O(n^1) O(n^{\log_b(a)})f(n)O(n)O(n1)O(nlogb​(a))情况2T ( n ) O ( n log ⁡ n ) T(n) O(n \log n)T(n)O(nlogn) 核心要点总结问题本质在约束条件下j ≥ i j \geq ij≥i找到最优的买卖组合分治法三步骤底只有一个市场时利润 S [ i ] − B [ i ] S[i] - B[i]S[i]−B[i]分将区间分成左右两部分合从三种情况中选择最优左、右、跨越中点关键技巧跨越中点时在左半部分找最低买入价在右半部分找最高卖出价复杂度O ( n log ⁡ n ) O(n \log n)O(nlogn)时间易错点不能直接使用左右子问题的解作为跨越中点的解合并步骤的时间复杂度是O(n)不是O(1) 拓展思考如果允许多次买卖这个问题会变成什么可以用动态规划解决吗如果允许往回开问题会变得更简单还是更复杂如果每个市场有交易成本算法需要如何修改与股票问题的区别为什么股票问题可以转化为最大子数组问题而这个问题不行 相关知识点分治法要点5-贪心法、分治法、动态规划主方法要点3-推导递推关系的渐进阶(主方法)算法复杂度分析要点2-比较不同函数的渐进阶大小记忆口诀分治买卖苹果左右分别求解跨越中点找最低买最高卖三者取最优