如果存在两个正常数c和N0，对于所有的N≥N0，有|f（N）|≤C|g（N）|，则记作：f（N）=O（g（N））。这时我们说f（N）的阶不高于g（N）的阶。
若存在两个正常数C和自然数N0，使得当N≥N0时有|f（N）|≥C|g（N）|，记为f（N）=Ω（g（N））。这时我们说f（N）的阶不低于g（N）的阶。
如果存在正常数c1，c2和n0，对于所有的n≥n0，有c1|g（N）|≤|f（N）|≤c2|g（N）|，则记作f（N）=（g，（N））。
O、Ω、Θ分别提供了算法运行时间的上界、下界、平均。
（简答题）
在算法复杂性分析中，O、Ω、Θ这三个记号的意义是什么？在忽略常数因子的情况下，O、Ω、Θ分别提供了算法运行时间的什么界？
正确答案
答案解析
略
相似试题
（填空题）
θ记号在算法复杂性的表示法中表示（）
（填空题）
常见的算法时间复杂度用大O记号表示为：常数阶（）、对数阶（）、线性阶（）、平方阶（）和指数阶（）。
（简答题）
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素，请设计一个最坏时间复杂度为O（n）的算法，并对其时间复杂度进行分析说明。
（简答题）
请用分治策略设计递归的归并排序算法，并分析其时间复杂性（要求：分别给出divide、conquer、combine这三个阶段所花的时间，并在此基础上列出递归方程，最后用套用公式法求出其解的渐进阶）。
（简答题）
已知有实现同一功能的两个算法，其时间复杂度分别为O（2n）和O（n10），假设现实计算机可连续运算的时间为107秒（100多天），又每秒可执行基本操作（根据这些操作来估算算法时间复杂度）105次。试问在此条件下，这两个算法可解问题的规模（即n值的范围）各为多少？哪个算法更适宜？请说明理由。
（填空题）
使用二分搜索算法在n个有序元素表中搜索一个特定元素，在最佳情况下，搜索的时间复杂性为O（），在最坏情况下，搜索的时间复杂性为O（）。
（简答题）
给定一个由n个数组成的序列，要求该序列的最长单调上升子序列，请设计对应的算法并分析其时间复杂度，如果时间复杂度劣于O（nlogn）的，将其优化为O（nlogn）时间复杂度的算法。
（单选题）
在n个结点的线性表的数组实现中，算法的时间复杂度是O（1）的操作是（）。
（判断题）
直接选择排序算法在最好情况下的时间复杂度为O（n）。
