Scholarlink

<p>Kurtz and Sidi (IEEE Trans Commun 36(12):1316–1323, 1988) have introduced an Optimal Nested Ordered (ONO) Group Testing procedure and proposed a recursive algorithm for its determination. Having <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\varvec{n}\)</EquationSource> </InlineEquation> items to be classified, the order of their algorithm is <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\varvec{O}\varvec{(}\varvec{n}^{\varvec{3}}\varvec{)}\)</EquationSource> </InlineEquation>. We discuss an alternative dynamic tree-based approach. It was discovered by Hwang (1973) fifteen years before the appearance of Kurtz and Sidi (IEEE Trans Commun 36(12):1316–1323, 1988) and remained unrecognized. It is an aim of this paper to link these two works. Our analysis demonstrates that Hwang’s version complexity is <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(\varvec{O}\varvec{(}\varvec{n}^{\varvec{2}}\varvec{\ln }\, \varvec{n}\varvec{)}\)</EquationSource> </InlineEquation> and in some special cases it can be reduced to <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(\varvec{O}\varvec{(}\varvec{n}^{\varvec{2}}\varvec{)}\)</EquationSource> </InlineEquation>.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

On the Optimal Nested Ordered Algorithm

  • 期刊论文

  • 发表日期：

    2025年10月24日

查看全文
  • Viktor Skorniakov

摘要

Kurtz and Sidi (IEEE Trans Commun 36(12):1316–1323, 1988) have introduced an Optimal Nested Ordered (ONO) Group Testing procedure and proposed a recursive algorithm for its determination. Having \(\varvec{n}\) items to be classified, the order of their algorithm is \(\varvec{O}\varvec{(}\varvec{n}^{\varvec{3}}\varvec{)}\) . We discuss an alternative dynamic tree-based approach. It was discovered by Hwang (1973) fifteen years before the appearance of Kurtz and Sidi (IEEE Trans Commun 36(12):1316–1323, 1988) and remained unrecognized. It is an aim of this paper to link these two works. Our analysis demonstrates that Hwang’s version complexity is \(\varvec{O}\varvec{(}\varvec{n}^{\varvec{2}}\varvec{\ln }\, \varvec{n}\varvec{)}\) and in some special cases it can be reduced to \(\varvec{O}\varvec{(}\varvec{n}^{\varvec{2}}\varvec{)}\) .