半平面交的新算法及其實用價值-資料下載頁
2025-06-19 17:56本頁面
【正文】 be called several times from Damp。C, requires O(n) number of calculations, wherefore it rises the total running time up. Besides, Samp。I calculates O(n) times in any case.l 如果給定半平面均在(189。π, 189。π]（或任意一個跨度為π的區(qū)間），Samp。I算法可被顯著縮短，C++程序只需要約二十行。USAICO比賽中就出現(xiàn)了這樣一題。Asymptotical Optimization to linear: The bottleneck of this algorithm is sorting. Pay attention the sorting is NOT a parison sort (sorting based on parison)! The key words for elements to be sorted are polar angles, which can be certainly determined by gradient – a decimal fraction. Since then, we can replace the O(nlogn) quicksort to O(n) radixsort. The asymptotical plexity of algorithm can decrease to O(n). Anyway O(n) approach usually runs slower than nlogn ones for its additional memory usage!本算法瓶頸是排序，這里的排序不是比較排序，因此可以將快速排序替換成基數(shù)排序，降低程序漸進時間復(fù)雜度到線性。The sentiment of my creation: An invention does not attribute to someone who es up with ideas. Most people have ideas. The difference between the average person and the inventor is that the inventor for some reason believes only himself, and has the urge to see his ideas through to fruition. Henri Matisse, a French painter and sculptor, ever said ‘there is nothing more difficult for a truly creative painter than to paint a rose, because before he can do so, he has first to forget all the roses that were ever painted.’ Equipped with both idealistic and practical spirit of innovation, I am on the way. How about you? Bibliography1. Kurt Mehlhorn. Data Structures and Algorithms Vol 3. SpringerVerlag, New York, 1984.2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to algorithms 2nd Edition. MIT Press, New York, 20013. Gill Barequet. Computational Geometry Lecture 4, Spring 2004/2005.4. Kavitha Telikepalli. Algorithms and Data Structures, Lecture 3, Winter 2003/2004.
研究報告相關(guān)推薦
鄂ICP備17016276號-1