A randomized algorithm for finding maximum with O((log n)2) polynomial tests

Hing F. Ting; Andrew C. Yao

doi:10.1016/0020-0190(94)90052-3

A randomized algorithm for finding maximum with O((log n)²) polynomial tests

Hing F. Ting
, Andrew C. Yao

电子与信息学部

Chinese University of Hong Kong

科研成果: 期刊稿件 › 文章 › 同行评审

6 引用（Scopus）

摘要

A well-known result by Rabin implies that n - 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c > 0, there is a randomized algorithm with error probability O(n^-c) for finding the maximum of n distinct real numbers using only O((log n)²) polynomial tests.

源语言	英语
页（从-至）	39-43
页数	5
期刊	Information Processing Letters
卷	49
期	1
DOI	https://doi.org/10.1016/0020-0190(94)90052-3
出版状态	已出版 - 14 1月 1994

访问文件

10.1016/0020-0190(94)90052-3

其它文件与链接

链接到 Scopus 的出版物

引用此

@article{f9e55c8c15f0485c86f2467bc3e5f62c,

title = "A randomized algorithm for finding maximum with O((log n)2) polynomial tests",

abstract = "A well-known result by Rabin implies that n - 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c > 0, there is a randomized algorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.",

keywords = "Algorithms, Decision trees, Maximum, Parity tests, Randomized algorithms",

author = "Ting, \{Hing F.\} and Yao, \{Andrew C.\}",

year = "1994",

month = jan,

day = "14",

doi = "10.1016/0020-0190(94)90052-3",

language = "英语",

volume = "49",

pages = "39--43",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - A randomized algorithm for finding maximum with O((log n)2) polynomial tests

AU - Ting, Hing F.

AU - Yao, Andrew C.

PY - 1994/1/14

Y1 - 1994/1/14

N2 - A well-known result by Rabin implies that n - 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c > 0, there is a randomized algorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.

AB - A well-known result by Rabin implies that n - 1 polynomial tests are necessary and sufficient in the worst case to find the maximum of n distinct real numbers. In this note we show that, for any fixed constant c > 0, there is a randomized algorithm with error probability O(n-c) for finding the maximum of n distinct real numbers using only O((log n)2) polynomial tests.

KW - Algorithms

KW - Decision trees

KW - Maximum

KW - Parity tests

KW - Randomized algorithms

UR - https://www.scopus.com/pages/publications/0028199378

U2 - 10.1016/0020-0190(94)90052-3

DO - 10.1016/0020-0190(94)90052-3

M3 - 文章

AN - SCOPUS:0028199378

SN - 0020-0190

VL - 49

SP - 39

EP - 43

JO - Information Processing Letters

JF - Information Processing Letters

IS - 1

ER -

A randomized algorithm for finding maximum with O((log n)2) polynomial tests

摘要

访问文件

其它文件与链接

学术指纹

引用此

A randomized algorithm for finding maximum with O((log n)²) polynomial tests