以演算法程式設計競賽試題為例使用Big-O AST靜態分析函式時間複雜度

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：98

、訪客IP：3.144.4.76

姓名

何東穎(Dong-Ying He) 查詢紙本館藏

畢業系所

軟體工程研究所

論文名稱

以演算法程式設計競賽試題為例使用Big-O AST靜態分析函式時間複雜度
(Static Analysis of Time Complexity with Big-O AST: A Case Study of Algorithmic Competitive Programming Problems)

相關論文

★ 條件判斷式事件驅動程式設計之C語言擴充	★ 基于小波变换的指纹活度检测,具有聚集 LPQ 和 LBP 特征
★ 應用自動化測試於異質環境機器學習管道之 MLOps 系統	★ 設計具有可視化思維工具和程式作為單一步的輔助學習程式之棋盤式遊戲
★ 流程圖式特定領域語言之設計與實作	★ TOCTOU 漏洞的靜態分析與實作
★ 用於繪製風力發電控制邏輯之特定領域語言	★ 在Java程式語言中以雙向結構表達數學公式間關聯之設計與實作
★ 支援模組化規則製作之程式碼轉換工具	★ 基於替代語意的 pandas DataFrame 靜態型別檢查器
★ 自動化時間複雜度分析的設計與實作–從軟體層面評估嵌入式系統的功率消耗	★ 以震波層析成像為應用之特定領域語言實作與分析
★ 用特徵選擇減少疲勞偵測腦電圖通道數	★ 一個應用紙本運算與數位化於程式設計學習使程序性思維可視化的機制
★ 基於抽象語法樹的陣列形狀錯誤偵測	★ 從合作學習角色分工獲得函式程式設計思維學習遞迴程式的機制

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

評估一演算法效率的好壞最常見方式是分析其演算法的時間複雜度。一般而言，時間複雜度的分析最常使用Big-O作為評估的標準。且時間複雜度的分析並非是一個簡單的問題，目前有許多研究探討使用靜態分析或動態分析的方式分析時間複雜度，本研究介紹了各個研究應用在程式設計競賽中的不足之處，並說明如何利用Big-O AST達到與程式語言無關，靜態分析函式時間複雜度的方法。
本研究提出從AST分析結構化程式設計中循序結構、重覆結構、選擇結構的時間複雜度的方法，並且考慮了函式呼叫的時間複雜度計算與遞迴的偵測。我們使用Python實作本研究，將工具命名為BigO-Calc。
本研究使用挑戰程序設計競賽書中演算法問題的五個演算法實作與本論文For迴圈$O(log(M))$的範例分析函式的時間複雜度。在六個範例共九個函式的時間複雜度分析上，BigO-Calc能夠正確的分析三個範例共五個函式的時間複雜度。

摘要(英)

The most common way to evaluate an algorithm is analyze the time complexity of target algorithm. In general, analyzing the time complexity of an algorithm is using big O notation. Time complexity analysis is not an easy question, there are many study of how to analyze time complexity by static analysis or dynamic analysis. We point out the weak point of others methodology applied to programming contest. In this paper, we present how to statically analyze function time complexity and how to do language independent analysis by Big-O AST.
In this paper, we present how to analyze the time complexity of this three architecture: sequence architecture, repetition architecture, selection architecture which are introduced by "structured programming". We also calculate function call′s time complexity and show how to detect recursion. We had implemented this tool by Python, and named BigO-Calc.
To evaluate BigO-Calc we analyze five algorithm questions which contain eight functions from book "挑戰程序設計", and one for loop example which the time complexity is $O(log(M))$. The result of evaluation is Big-O Calc can analyze five functions from three algorithm questions.

關鍵字(中)

★ 靜態分析
★ 抽象語法樹
★ 大O符號
★ 時間複雜度
★ 演算法

關鍵字(英)

★ Static Analysis
★ Abstract Syntax Tree
★ Big-O
★ Time Complexity
★ Algorithm

論文目次

一、緒論1
1.1 演算法程式設計競賽................................................... 1
1.2 多數演算法程式設計競賽採用動態分析分析時間複雜度...... 2
1.3 時間複雜度與Big-O.................................................... 2
1.4 程式碼分析............................................................... 3
1.5 目前針對時間複雜度分析的方法在演算法程式設計競賽中
的適切性......................................................................... 4
1.5.1 從測試資料集變化分析....................................... 5
1.5.2 從中介碼、機械碼分析....................................... 5
1.5.3 從控制流程圖分析............................................. 6
1.5.4 從抽象語法樹進行靜態分析................................. 7
二、動機8
2.1 以演算法程式設計競賽試題為例.................................... 8
2.2 本研究開發一靜態分析工具.......................................... 12
2.3 相關研究應用於演算法程式設計競賽.............................. 13
2.3.1 Complexity....................................................... 14
2.3.2 Automated Big-O Analysis of Algorithms ................ 15
2.3.3 CAMPY .......................................................... 16
2.3.4 ALGator.......................................................... 16
2.3.5 Asymptus ........................................................ 17
三、使用Big-O AST 靜態分析函式時間複雜度18
3.1 Big-O AST................................................................ 18
3.2 時間複雜度計算......................................................... 19
3.2.1 循序結構複雜度分析.......................................... 19
3.2.2 選擇結構複雜度分析.......................................... 20
3.2.3 重覆結構複雜度分析.......................................... 21
3.2.4 函式呼叫分析................................................... 24
四、實作26
4.1 抽象語法樹生成階段................................................... 28
4.2 抽象語法樹轉換階段................................................... 29
4.3 時間複雜度計算階段................................................... 30
4.4 時間複雜度化簡階段................................................... 31
五、評估33
5.1 評估函式時間複雜度分析的正確性................................. 33
5.2 分析與解釋............................................................... 34
5.3 評估總結.................................................................. 35
六、相關研究36
6.1 A Novel Method to Find Time Complexity of an Algorithm
by Using Control Flow Graph............................................... 36
6.2 An Abstract to Calculate Big O Factors of Time and Space
Complexity of Machine Code................................................ 37
七、未來展望38
八、結論39
參考文獻40

參考文獻

[1] 何東穎、莊永裕, “使用AST 進行靜態程式碼分析函式時間複雜度,” TANET 2018,
pp. 1–6, 2018 臺灣網際網路研討會, 2018.
[2] “icpc 官方網站.” https://icpc.baylor.edu/.
[3] J. Hartmanis and R. E. Stearns, “On the computational complexity of algorithms,”
Transactions of the American Mathematical Society, vol. 117, pp. 285–306, 1965.
[4] D. E. Knuth, The Art of Computer Programming, Volume 3: (2Nd Ed.) Sorting and
Searching. Redwood City, CA, USA: Addison Wesley Longman Publishing Co., Inc.,
1998.
[5] S. C. Johnson, “Lint, a c program checker,” in COMP. SCI. TECH. REP, pp. 78–
1273, 1978.
[6] S. L. Graham, P. B. Kessler, and M. K. Mckusick, “Gprof: A call graph execution
profiler,” in Proceedings of the 1982 SIGPLAN Symposium on Compiler Construction,
SIGPLAN ’82, (New York, NY, USA), pp. 120–126, ACM, 1982.
[7] R. Vaz, V. Shah, A. Sawhney, and R. Deolekar, “Automated big-o analysis of algorithms,”
in 2017 International Conference on Nascent Technologies in Engineering
(ICNTE), pp. 1–6, Jan 2017.
[8] M. Rav, “Complexity.” https://github.com/Mortal/complexity.
[9] T. Dobravec, “Estimating the time complexity of the algorithms by counting the
java bytecode instructions,” in 2017 IEEE 14th International Scientific Conference
on Informatics, pp. 74–79, Nov 2017.
[10] A. Srikanth, B. Sahin, and W. R. Harris, “Complexity verification using guided
theorem enumeration,” in Proceedings of the 44th ACM SIGPLAN Symposium on
Principles of Programming Languages, POPL 2017, (New York, NY, USA), pp. 639–
652, ACM, 2017.
[11] F. Demontiê, J. Cezar, M. Bigonha, F. Campos, and F. Magno Quintão Pereira,
“Automatic inference of loop complexity through polynomial interpolation,” in Proceedings
of the 19th Brazilian Symposium on Programming Languages - Volume 9325,
(New York, NY, USA), pp. 1–15, Springer-Verlag New York, Inc., 2015.
[12] S. Gayathri Devi, K. Selvam, and S. P. Rajagopalan, “An abstract to calculate big o
factors of time and space complexity of machine code,” in International Conference
on Sustainable Energy and Intelligent Systems (SEISCON 2011), pp. 844–847, July
2011.
[13] K. S. Kumar and D. Malathi, “A novel method to find time complexity of an algorithm
by using control flow graph,” in 2017 International Conference on Technical
Advancements in Computers and Communications (ICTACC), pp. 66–68, April 2017.
[14] 秋葉拓哉, 岩田陽一, 北川宜稔, et al., 挑戰程序設計競賽（第2 版）. 人民郵電出
版社, 第2 版ed. 巫澤俊, 莊俊元, 李津羽.
[15] “Bigo-calc.” https://github.com/ncu-psl/BigO-Calc.
[16] “Soot framework.” http://sable.github.io/soot/.
[17] “Z3 theorem prover.” https://github.com/Z3Prover/z3.
[18] E. W. Dijkstra, “Structured programming,” ch. Chapter I: Notes on Structured Programming,
pp. 1–82, London, UK, UK: Academic Press Ltd., 1972.
[19] “Java 版本實作.” https://github.com/ncu-psl/BigO-Calc/tree/origin-javacalc,
2018. 已停止維護.
[20] T. Parr, The Definitive ANTLR 4 Reference. Pragmatic Bookshelf, 2nd ed., 2013.
[21] E. Bendersky, “pycparser.” https://github.com/eliben/pycparser.
[22] C. Thunes, “javalang.” https://github.com/c2nes/javalang.
[23] A. S. Novikov, A. N. Ivutin, A. G. Troshina, and S. N. Vasiliev, “The approach to
finding errors in program code based on static analysis methodology,” in 2017 6th
Mediterranean Conference on Embedded Computing (MECO), pp. 1–4, June 2017.
[24] “Sympy 官方網站.” https://www.sympy.org/en/index.html.
[25] “Domjudge 官方網站.” https://www.domjudge.org/.
[26] “青島大學線上評判系統(qduoj).” https://qduoj.com/.

指導教授

莊永裕(Yung-Yu Zhuang)

審核日期

2019-6-26

推文