教學用靜態時間複雜度分析工具;A Static Time Complexity Analysis Tool for Education

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/86501

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/86501

Title:	教學用靜態時間複雜度分析工具;A Static Time Complexity Analysis Tool for Education
Authors:	蔡家豪;Cai, Jia-Hao
Contributors:	資訊工程學系
Keywords:	時間複雜度;遞迴函式;靜態程式分析;抽象語法樹分析;Time complexity;Recursive function;Static program analysis;Abstract syntax tree analysis
Date:	2021-07-20
Issue Date:	2021-12-07 12:54:29 (UTC+8)
Publisher:	國立中央大學
Abstract:	程式碼的好壞可以從很多面向來分析。學習者可以從這些評分指標中，學習如何撰寫更好的程式碼。評分者也能藉由評分工具來對程式碼進行程式功能正確與否以外的評價。其中，時間複雜度是評價程式碼好壞與否的重要指標。但分析程式碼的時間複雜度並不是簡單的事。本研究實作一個基於抽象語法樹分析的程式碼時間複雜度靜態分析工具－－RecTCC。現有的基於抽象語法樹分析的工具，因為能獲得的資訊不足，對於遞迴函式的支援性不佳。RecTCC利用Value Numbering的概念及符號表來追蹤函式參數，找出參數與引數之間的值的變化，並以此來當作遞迴呼叫的工作量變化。Big-O AST會在AST上記錄各節點的時間複雜度，走訪Big-O AST並計算循序、選擇、重覆結構的時間複雜度，可找出非遞迴呼叫部份的部份時間複雜度。由以上步驟可以得到遞迴關係式，再搭配Master Theorem來分析遞迴函式的時間複雜度。本研究將Introduction of Algorithms一書中的演算法分成三類：Loop、If-Else、Recursion，並從各類中挑選演算法來實作並進行評估。與其他工具相比，只有RecTCC對這三類演算法皆有支援。;There are several aspects to judge the quality of a source code. Students can learn how to write a better code from these evaluation features. Teachers can evaluate the source code besides the correctness of programs. In these evaluation features, the time complexity is an important feature. However, finding the time complexity of a source code is difficult. In this paper, we implement a static time complexity analysis tool based on AST analysis, called RecTCC. Because of the lack of some information, present analysis tools based on AST analysis are not compatible with recursive functions. RecTCC uses the concept of Value Numbering and symbol tables to chase the function parameters. We take the variations between parameters and arguments as the workload variation of the recursive calls. RecTCC uses Big-O AST to find the time complexities comprised of the non-recursive call parts. Finally, RecTCC can find the time complexities of recursive functions by recurrence relations and the master theorem. In this paper, we separate algorithms in "Introduction of Algorithms" into three categories: Loop, If-Else, Recursion. We implement some algorithms from these categories, and use them to test analysis tools. RecTCC is the only tool compatible with all algorithms in these three categories.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	63	View/Open

社群 sharing

Loading...