DSpace About DSpace Software

SEIKEI University Repository >
01:紀要(Bulletin) >
11:理工学研究報告 >
第58巻第2号 >

Please use this identifier to cite or link to this item: http://hdl.handle.net/10928/1492

Title: 少ないメモリで動作するアルゴリズム
Other Titles: Algorithms Running with Small Memory
Authors: 清見, 礼
KIYOMI, Masashi
Keywords: space efficient algorithm
longest increasing subsequence
longest common substring
Issue Date: 1-Dec-2021
Publisher: 成蹊大学理工学部
Abstract: Most of the researches in algorithms are for reducing computational time complexity. Such researches often neglect the amount of memory used, resulting in algorithms that require large amounts of memory and cannot be executed on ordinary PCs. On the other hand, there have been researches on reducing the amount of memory required for computation for a long time. However while most of them were theoretically interesting, practically too restrictive, such as whether some computation can be done with O(log n) bits for input size n. In recent years, the use of big data has become widespread, and the size of the input to algorithms tends to increase compared to the past. In the past, it was natural to use the same amount of memory as the size of the input data, and this was not a problem. However, if we consider an example of input data filling a hard disk, it becomes unrealistic to use the same amount of memory as the input data, as the capacity of a hard disk is generally much larger than the capacity of memory. Against this background, we consider algorithms that handle big data using less memory than the size of the input data. In this paper, the author outlines an example of such research that he has recently conducted.
URI: http://hdl.handle.net/10928/1492
Appears in Collections:第58巻第2号

Files in This Item:

File Description SizeFormat
rikougaku-58-2_25-28.pdf627.78 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


Valid XHTML 1.0! DSpace Software Copyright © 2002-2010  Duraspace - Feedback