论文部分内容阅读
本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。
某些算法时间复杂性的下界
【摘 要】
：
本文定义了两类机器,并讨论了在这两类机器上完成某类作业所需时间的下界。其中包括:在n个排好序的有理数中同时查询n个数至少需时cn log n;把n个有理数按大小排列分类至少需时cn log n,其中c为某个常数。
【出 处】
：
中国科学
【发表日期】
：
1979年05期
其他文献
本文根据中国的天山、祁连山、秦岭和昆仑-唐古拉地槽褶皱带的发展特点,结合国外的塔斯曼地槽、阿帕拉契地槽和科迪勒拉地槽的实际资料,讨论了地槽发展规律,否定并批判了Stille的单旋迥说,提出地槽发展的多旋迥说,初步建立了多旋迥发展模式,当前流行的板块构造说,与多旋迥说不但不互相排斥,而且可以互相补充,密切结合,地槽褶皱带的发展有明显的迁移方向,而且有横向迁移和纵向迁移之别.板块活动也显示向洋迁移特点
期刊
本文证明了如下“抉择性”结果:设G是一局部紧群,{T_k)是B到L~g(G)内的有界卷积算子的序列(B是由Haar可测函数构成的平移不变Banach空间).设对所有f∈D,{T_kf(x)}都a.e.收敛于一个本性有界函数,这里D是B的任意一个稠密子集.则或者对所有f∈B,T_kf(x)都a.e.收敛,或者存在至少一个f∈B,使得T_kf(x)a.e.发散。
期刊
本文提出了具有某种规范对称性的时空几何性质,应当由有同样规范对称性物质的物理性质决定.由此分别提出了以Lorentz群、Poincaré群和de Sitter群作为规范群的引力规范理论方案,所有这些方案都不与现有的实验和观测相矛盾,并有可能为解决广义相对论中的奇性和不可重整的困难提供一些线索。
期刊
本文应用电子显微技术对斜纹夜蛾核型多角体病毒形态和精细结构进行了研究,病毒多角体在扫描电子显微镜下观察表面是皱褶不平的,多角体切片的蛋白质晶格与多角体经碱溶解后所见块状蛋白质晶格相同,其晶格间距约为20埃,多角体蛋白质晶格的亚单位呈六角形,病毒粒子在病毒束内呈不对称性排列,数目不恒定,病毒粒子的螺旋结构为13—15螺转,螺距约为150埃。
期刊
本文直接由辐射场方程与边界条件导出了高速流动激光器的稳定振荡条件,指出了文献[1]所假定的稳定振荡条件仅在一定条件下近似成立,用本文得到的稳定振荡条件与文献[2]的饱和增益公式导出了GDL输出功率表达式,指出了输出功率与GDL各种参量之间的关系,用几何光学近似导出了光腔模式的解析表达式,指出了充有流动激活介质的Fabry-Perot腔的模式结构与特征.文中对Gerry的典型
期刊
本文应用Grad的十三矩量方法,讨论有电磁场、重力场作用的多元系稀薄气体中的输运现象,得到了Boltzmann方程的近似解和计算输运系数的公式.所得结果,在特定条件下与Chapman,Enskog与Hirschfelder等人所得的理论结果一致.文中并提出了一个计算部分电离气体电导率的公式。文中还计算了氮气由室温至8000K的粘滞系数、由室温至20000K的导热系数和由8000 K至20000 K
期刊
本文研究了当初值是任意有界的Lebesgue可测函数时,单个守恒律的解的整体性质,证明了任意激波曲线除去至多可数个点外,处处有切线,而且切线的斜率构成一个局部有界变差函数,我们证明激波构成的集合是零测度的Borel集合,并证明甚至存在C~∞初值,相应的激波条数是不可数的,从而否定了关于激波条数至多可数的论断.本文还揭示了激波集合在上半平面的拓扑图景,除去至多两个外,它的其余的连通分支都各自包含在一
期刊
本文简要综述与静电场作用下α-碘酸锂单晶的衍射光强变化有关的一系列现象,并判定引起光衍射增强的主要机理是:静电场作用下,空间电荷在准周期层状缺陷处富集,显著加强了各层间折射率准周期的不均匀性,形成与α-碘酸锂单晶对称性相一致的六角锥状位相型空间光栅结构,本文还计算了其衍射光空间频谱谱线取向,结果与实验相符。
期刊
本文采用流体动力学模型,研究了有限厚度的盘状星系对称面上的松卷螺旋密度波,文中推出了准单色波传播的基本方程式,并以Toomre(N=2)的质量模型为例进行了数据计算.结果表明:松卷螺旋密度波的特性与紧卷螺旋密度波有着相当明显的差别,一般说来,由于存在“松卷效应”,实波数的线性密度波总是不稳定的,对于曳型波而言,波将在共转圈内不断增长;在共转固外不断衰减;对于导型波而言,则恰恰相反。
期刊
在背联体棘尾虫上发现了各种式样的大核调节现象,这些大核调节现象都是在背联体棘尾虫保持完满正常的外形下进行的,反映出背联体棘尾虫的细胞质比它的核器稳定。如果相联二虫细胞质间的协调和均衡发生变化,大核则总是随着起变化,表现为向突出的细胞质部分伸展.摘除全部大核的实验进一步表明,背联体棘尾虫的外部形态稳定与否主要是与细胞质有关。
期刊