对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列（TSC）的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。     

Insertion Sort is O(n log n)

Traditional Insertion Sort runs in O(n²) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that Gapped Insertion Sort has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability.     

Sorting Stably,in Place,with O(n log n) Comparisons and O(n) Moves

We settle a long-standing open question, namely whether it is possible to sort a sequence of n elements stably (i.e., preserving the original relative order of the equal elements), using O(1) auxiliary space and performing O(n log n) comparisons and O(n) data moves. Munro and Raman stated this problem in J. Algorithms (13, 1992) and gave an in-place but unstable sorting algorithm that performs O(n) data moves and O(n^1+ε) comparisons. Subsequently (Algorithmica, 16, 1996) they presented a stable algorithm with these same bounds. Recently, Franceschini and Geffert (FOCS 2003) presented an unstable sorting algorithm that matches the asymptotic lower bounds on all computational resources.     

IM-FTS:一种快速增量式频繁访问序列挖掘算法

由于Web数据增长迅速,先前的频繁序列随着序列库的更新而改变。若重新挖掘频繁序列会增加处理时间和数据存储量。提出一种改进的扩展格结构IE-LATTICE,存储先前的挖掘结果,并在其基础上提出一种基于双向约束的增量挖掘算法IM-FTS,在利用先前结果和约束策略前提下,算法仅从插入和删除序列中发现新的频繁序列。分析和实验表明算法能有效缩减数据处理时间和存储空间。     

O(n) routing in rearrangeable networks

In (2n−1)-stage rearrangeable networks, the routing time for any arbitrary permutation is Ω(n²) compared to its propagation delay O(n) only. Here, we attempt to identify the sets of permutations, which are routable in O(n) time in these networks. We define four classes of self-routable permutations for Benes network. An O(n) algorithm is presented here, that identifies if any permutation P belongs to one of the proposed self-routable classes, and if yes, it also generates the necessary control vectors for routing P. Therefore, the identification, as well as the switch setting, both problems are resolved in O(n) time by this algorithm. It covers all the permutations that are self-routable by anyone of the proposed techniques. Some interesting relationships are also explored among these four classes of permutations, by applying the concept of ‘group-transformations’ [N. Das, B.B. Bhattacharya, J. Dattagupta, Hierarchical classification of permutation classes in multistage interconnection networks, IEEE Trans. Comput. (1993) 665–677] on these permutations. The concepts developed here for Benes network, can easily be extended to a class of (2n−1)-stage networks, which are topologically equivalent to Benes network. As a result, the set of permutations routable in a (2n−1)-stage rearrangeable network, in a time comparable to its propagation delay has been extended to a large extent.     

An O(n) bin-packing algorithm for uniformly distributed data

We give a first-fit type algorithm, with running timeO(n), for the classical one-dimensional bin-packing problem, and examine it from a probabilistic point of view. Our main result is that the expected waste for this algorithm isO(n ^2/3).     

A Deterministic Construction of Normal Bases With Complexity O(n3 + n log n log(log n) log q)

Constructing normal bases of GF(qⁿ) over GF (q) can be done by probabilistic methods as well as deterministic ones. In the following paper we consider only deterministic constructions. As far as we know, the best complexity for probabilistic algorithms is O(n² log⁴n log² (log n) + n log n log (log n) log q ) (see von zur Gathen and Shoup, 1992). For deterministic constructions, some prior ones, e.g. Lueneburg (1986), do not use the factorization of Xⁿ - 1 over GF(q). As analysed by Bach, Driscoll and Shallit (1993), the best complexity (from Lueneburg, 1986) is O(n³ log n log(log n) + n² log n log(log n) log q). For other deterministic constructions, which need such a factorization, the best complexities are O(n^3,376 + n² log n log(log n) log q) (von zur Gathen and Giesbrecht, 1990), or O(n³ log q); see Augot and Camion (1993). Here we propose a new deterministic construction that does not require the factorization of Xⁿ - 1. Its complexity is reduced to O (n³ + n log n log(log n) log q ).     

An O(n 1.5 ) Deterministic Gossiping Algorithm for Radio Networks

We consider the problem of distributed gossiping in radio networks of unknown topology. For radio networks of size n and diameter D , we present an adaptive deterministic gossiping algorithm of time O ($\sqrt{D}$ n+n log 2 n ) or O(n 1.5) . This algorithm is a tuned version of the fastest previously known gossiping algorithm due to Gasieniec and Lingas [1], and improves the time complexity by a poly-logarithmic factor.     

边赋权森林ω-路划分的O(n)算法

ω-路划分问题是路划分问题的一般化,它源于并行计算机系统、计算机网络与分布式控制系统等一类广播通信问题.设置最少的信息源节点,使得在指定的时间内将信息源节点所拥有的信息发送到其余节点,并且保证不同通信线路之间不得相交.从Hamilton路的NP-完全性不难看出,ω-路划分问题属于NP-完全问题.通过构造性证明技术,获得了边赋非负权路径、树和森林的ω-路划分问题的一些性质.分别提出了求解边赋非负权路径和边赋非负权树的ω-路划分问题的线性时间算法,讨论了算法的局部实现技术,详细地分析了这些算法的复杂度.以这两个算法为基础,提出了一个线性时间算法求解边赋非负权森林的ω-路划分问题.所提出的算法直观简明、操作容易,只需要较少的运行时间和较小的存储空间.     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n^2)．     

An O(log n) algorithm for parallel update of minimum spanning trees

Parallel algorithms are presented for updating a minimum spanning tree when the cost of an edge changes or when a new node is inserted in the underlying graph. Our model of computation is a parallel random access machine which allows simultaneous reads but prohibits simultaneous writes into the same memory location. The algorithms described in this paper for updating a minimum spanning tree require O(log n) time and O(n²) processors. These algorithms are efficient when compared to previously known algorithms for initial construction of a minimum spanning tree that require O(log²n) time and use O(n²) processors. The two main contributions of this paper are: (i) usage of an inverted tree for updating minimum spanning trees, and (ii) discovery of an interesting property of minimum spanning trees that we exploit to develop a novel algorithm for vertex insertion update.     

具有O(n)时间复杂度的分布式请求集生成算法

在大规模完全分布式系统的互斥问题上,快速生成请求集是必要的。在基于松弛差集的相关原理上,引入了二次松弛差集的概念。经分析相关概念及定理,将原本“求差”的过程变为“求和”的过程;进而利用 “求和”步骤间的递推关系,大大减少了求和步骤,使整个算法的时间复杂度控制在O(n)。与时间复杂度同为O(n^2)的其他经典算法相比,生成的请求集长度仍保持在2n^(1/2)的数量级。     

An O(n) algorithm for computing the set of available expressions of D-charts

Summary In this paper, an idea for computing the set of available expressions at entrance to the nodes of D-charts is explained. An algorithm based on the idea will work in time O(n), given bit vector operations, where n is the number of nodes. D-charts are flow graphs which correspond to the programs where ifs and whiles are used as control statements. The paper is based on the authors' previous report [9].     

An O(n log n) Average Time Algorithm for Computing the Shortest Network under a Given Topology

In 1992 F. K. Hwang and J. F. Weng published an O(n ² ) time algorithm for computing the shortest network under a given full Steiner topology interconnecting n fixed points in the Euclidean plane. The Hwang—Weng algorithm can be used to improve substantially existing algorithms for the Steiner minimum tree problem because it reduces the number of different Steiner topologies to be considered dramatically. In this paper we present an improved Hwang—Weng algorithm. While the worst-case time complexity of our algorithm is still O(n ² ) , its average time complexity over all the full Steiner topologies interconnecting n fixed points is O (n log n ). Received August 24, 1996; revised February 10, 1997.     

A new hardware-assisted PIR with O(n) shuffle cost

Since the concept of private information retrieval (PIR) was first formalized by Chor et al., various constructions have been proposed with a common goal of reducing communication complexity. Unfortunately, none of them is suitable for practical settings mainly due to the prohibitively high cost for either communications or computations. The booming of the Internet and its applications, especially, the recent trend in outsourcing databases, fuels the research on practical PIR schemes. In this paper, we propose a hardware-assisted PIR scheme with a novel shuffle algorithm. Our PIR construction entails O(n) offline computation cost, and constant online operations and O(log n) communication cost, where n is the database size.