检索结果-内蒙古大学图书馆

THEORETICAL COMPUTER SCIENCE 2022年 916卷 62-69页

作者： Katoh, Takashi Goto, Keisuke Fujitsu Labs Ltd Kawasaki Japan

An initializable array is an array that supports the read and write operations for any element and the initialization of the entire array. This paper proposes a simple in-place algorithm to implement an initializable array of length N containing l is an element of O(w) bits entries in Nl+ 1 bits on the word RAM model with w bits word size, i.e., the proposed array requires only 1 extra bit on top of a normal array of length N containing l bits entries. Our algorithm supports the all three operations in constant worst-case time, that is, it runs in-place using at most constant number of words O(w) bits during each operation. The time and space complexities are optimal since it was already proven that there is no implementation of an initializable array with no extra bit supporting all the operations in constant worst-case time (Hagerup and Kammer, 2017 [12]). Our algorithm significantly improves upon the best algorithm presented in the earlier studies (Navarro, 2014 [5]) which uses N + o(N) extra bits to support all the operations in constant worst-case time. (c) 2022 Elsevier B.V. All rights reserved.

关键词： In-place algorithm Space efficient data structure initializable array

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：