网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的词汇:

 

词汇 Sparse set
分类 英语词汇 英语翻译词典
释义

Sparse set

中文百科

稀疏语言 Sparse language

(重定向自Sparse set)

在计算复杂性理论里面, 稀疏语言是一种形式语言 (一堆字串的集合字串),并且这语言内长度为n的字串个数,被一个n的多项式所限制住。 这种语言主要被用来研究NP这类语言与其他种类语言的关系。包含所有稀疏语言的复杂度类被称作SPARSE

稀疏语言会被叫做稀疏的原因是因为,对任何语言,长度为n的字串可能性个数总共有2个,而如果某特定语言只有包含这一些字串里面的多项式个数个,那这语言所包含字串的比例会随着n的成长很快的减少。 所有一元语言都是稀疏语言。一个稀疏语言比较不单纯的例子是,某个语言包含所有恰有k个1(k是某个常数)的二进位字串,; 对任何长度n, 这个语言仅包含\binom{n}{k}个字串, 而这个数字则被 n给限制住。

英语百科

Sparse language 稀疏语言

(重定向自Sparse set)

In computational complexity theory, a sparse language is a formal language (a set of strings) such that the complexity function, counting the number of strings of length n in the language, is bounded by a polynomial function of n. They are used primarily in the study of the relationship of the complexity class NP with other classes. The complexity class of all sparse languages is called SPARSE.

随便看

 

依恋情感网英汉例句词典收录3870147条英语例句词条,基本涵盖了全部常用英语单词的释义及例句,是英语学习的有利工具。

 

Copyright © 2004-2024 Yiyi18.com All Rights Reserved
京ICP备2021023879号 更新时间:2025/10/16 13:06:30