简答题

在算法复杂性分析中,O、Ω、Θ这三个记号的意义是什么?在忽略常数因子的情况下,O、Ω、Θ分别提供了算法运行时间的什么界?

正确答案

如果存在两个正常数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记号表示为:常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。

    填空题查看答案

  • 给定线性序集中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)。

    判断题查看答案