CAJ | 학술논문

目前,基于排序的等价类生成算法存在以下不足:排序后仍需高达O(∣B‖U∣)的时间复杂度重复进行运算才求得等价类,为此,设计了一种新算法.新算法采用孩子兄弟表示法,将生成等价类的过程定义为一棵二叉树,主要采取了边生成节点边访问,一旦求得某个等价类便释放相应分支节点空间的方法.其时间复杂度为O(∣C‖U∣),空间复杂度为O(∣U∣),为求等价类提供了一个新的解决办法.
목전,기우배서적등개류생성산법존재이하불족:배서후잉수고체O(∣B‖U∣)적시간복잡도중복진행운산재구득등개류,위차,설계료일충신산법.신산법채용해자형제표시법,장생성등개류적과정정의위일과이차수,주요채취료변생성절점변방문,일단구득모개등개류편석방상응분지절점공간적방법.기시간복잡도위O(∣C‖U∣),공간복잡도위O(∣U∣),위구등개류제공료일개신적해결판법.
At present, the algorithm for generating equivalence class based on sorting has the following shortcoming: for computing the equivalence class, it had to repeat the same operation after sorting, and its time complexity is as high as 0 (∣B‖U∣). For improving the efficiency of the algorithm for computing equivalence class, this paper designed a novel algorithm. In the new algorithm, used the child-brother storage structure form, and defined the process of generating equivalence class as a binary tree. The designed method of the new algorithm was that the node of the binary tree was being visited when it was being created, and once a equivalence class was obtained, the corresponding node would be released. Time complexity and the space complexity of the new algorithm are O(∣C‖U∣) and O(∣U∣) respectively. It provided a new method to compute the equivalence class of the universe U.