【算法】算法设计与分析 期末复习总结 |
您所在的位置：网站首页 › 电路与电子技术基础考试重点知识归纳 › 【算法】算法设计与分析 期末复习总结 |
【算法】算法设计与分析 期末复习总结
|
第一章 算法概述
时间复杂度比大小，用代入法，代入2即可。求渐进表达式，就是求极限，以极限为O的括号；O是指上界，Ω是指下界，θ是指上下界相等，在这里，可以这样理解：
f(n) = O(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 大；f(n) = Ω(g(n)) 意味着 g(n) 在 n 趋近于无穷大时比 f(n) 小；f(n) = θ(g(n)) 意味着 g(n) 在 n 趋近于无穷大时和 f(n) 同阶；
第二章 递归与分治
主定理要掌握，选择题必考：
填空有一道二分搜索，掌握简单版和改进版即可： #include using namespace std; const int N = 1e6 + 10; int n, m, a[N], x; int bisearch(int x, int a[], int left, int right) { if (left > right) return -1; int middle = (left + right) / 2; if (a[middle] == x) return middle; else if (a[middle] < x) return bisearch(x, a, left, middle - 1); else return bisearch(x, a, middle + 1, right); } int main() { cin >> n >> m; for (int i = 0; i < n; i++) cin >> a[i]; while (m--) { cin >> x; cout n >> m; for (int i = 0; i < n; i++) cin >> a[i]; while (m--) { cin >> x; pair p = bs(x, a, 0, n - 1); cout |
【本文地址】
今日新闻 |
推荐新闻 |