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

NCUIR > College of Electrical Engineering & Computer Science > Software Engineer > Electronic Thesis & Dissertation > Item 987654321/80946

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

Title:	以演算法程式設計競賽試題為例使用Big-O AST靜態分析函式時間複雜度;Static Analysis of Time Complexity with Big-O AST: A Case Study of Algorithmic Competitive Programming Problems
Authors:	何東穎;He, Dong-Ying
Contributors:	軟體工程研究所
Keywords:	靜態分析;抽象語法樹;大O符號;時間複雜度;演算法;Static Analysis;Abstract Syntax Tree;Big-O;Time Complexity;Algorithm
Date:	2019-06-26
Issue Date:	2019-09-03 15:20:42 (UTC+8)
Publisher:	國立中央大學
Abstract:	評估一演算法效率的好壞最常見方式是分析其演算法的時間複雜度。一般而言，時間複雜度的分析最常使用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.
Appears in Collections:	[Software Engineer] Electronic Thesis & Dissertation

Files in This Item:

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

社群 sharing

Loading...