算法合集之半平面交的新算法及其實(shí)用價(jià)值(參考版)
2024-10-19 20:30本頁面
【正文】 。 山， 刺破青天鍔未殘。 山， 倒海翻江卷巨瀾。 Anyway O(n) approach usually runs s lowe r th an n logn on es fo r its additional memory usage! November 12, 2021 Zeyuan Zhu 47 5. Conclusion and Practical Use 美麗心靈 諾貝爾獎(jiǎng)得主 John Nash 原創(chuàng)的理論 ——original idea 創(chuàng)新與信息學(xué)競賽 創(chuàng)新與技術(shù) 我心目中的創(chuàng)新 ——最重要的是 思想創(chuàng)新 ， 其次是 行為 創(chuàng)新 ， 再其次是文章創(chuàng)新 ， 再再其次才是語言創(chuàng)新 思想 實(shí)踐 The principal mark of genius is not perfection but originality, the opening of new frontiers. Authur Koestler (1905 1983) Hungarianborn British writer and jounalist. November 12, 2021 Zeyuan Zhu 48 5. Conclusion and Practical Use 創(chuàng)新如高山 山， 快馬加鞭未下鞍。 USAICO比賽中就出現(xiàn)了這樣一題 。π]（ 或任意一個(gè)跨度為 π的區(qū)間 ） ， Samp。C program may not. An informatics problem a p p e a r e d in U S A I n v i t a t i o n a l Computing Olympiad contest with such purpose. 如果給定半平面均在 (189。π] (or any span of π), Samp。 November 12, 2021 Zeyuan Zhu 45 5. Conclusion and Practical Use If the given hplanes are all in (189。I程序比 Damp。I算法復(fù)雜度中的系數(shù) ， 遠(yuǎn)小于Damp。I program runs approx five times faster than Damp。I a lgor ithm’ s c omplex ity is extraordinarily smaller than Damp。C大大簡單化 ， C++程序語言實(shí)現(xiàn)Samp。C one. The program in C++ programming language takes less than 3KB. 新的 Samp。 November 12, 2021 Zeyuan Zhu 43 5. Conclusion and Practical Use It is much easier to code Samp。I算法似乎和 Damp。C algorithm, but some overwhelming advantages of implementing Samp。通常我們用快速排序?qū)崿F(xiàn) Step2，總的時(shí)間復(fù)雜度為O(nlogn)，隱蔽其中的 常數(shù)因子 很小 November 12, 2021 Zeyuan Zhu 41 5. Conclusion and Practical Use 總結(jié)和實(shí)際應(yīng)用 November 12, 2021 Zeyuan Zhu 42 5. Conclusion and Practical Use Great ideas need landing gear as well as wings. Samp。I algorithm remain linear – O(n) running time. Usually we use quicksort. The total plexity is O(nlogn), with fairly small constant factor hidden. ? 除了 Step2中的排序以外， Samp。π]∪ (189。π, 189。π]∪ (189。π, 189。π, π] gives a lower hull. November 12, 2021 Zeyuan Zhu 34 4. SortandIncremental Algorithm ?相鄰半平面的交點(diǎn)組成半個(gè)凸多邊形。π] gives an upper hull and (π, 189。π, π]給出下半個(gè) ? Step 4: Intersections of adjacent hplane pairs in stack form half a convex polygon. For the two sets, we have two halves – (189。π]給出上半個(gè)， (π, 189。我們有兩個(gè)點(diǎn)集， (189。 ? Step 3: If this intersection is to the right of the intersection of top two hplanes in stack, we pop the stack once. November 12, 2021 Zeyuan Zhu 31 4. SortandIncremental Algorithm ? Step 3: November 12, 2021 Zeyuan Zhu 32 4. SortandIncremental Algorithm ?前問我們說到出棧，出棧只需要一次么？ Nie!我們要繼續(xù)交點(diǎn)檢查，如果還在右邊我們要繼續(xù)出棧，直到 當(dāng)前交點(diǎn)在棧頂
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1