【CSP-J】初赛知识点

经验分享区
1

2024年08月10日是个可爱的日子，我们进行了一场有(kong)趣(bu)的考试——因为电脑没网了，@信友队蔡老师 大(纯)发(属)慈(故)悲(意)地让我们考试。

但他没有打印机，花了270￥ :upside_down_face:

为了让他的270￥不打水漂， 本蒟蒻决定写个帖子，总结一下考试

一、时间复杂度

时间复杂度是衡量算法执行时间随输入数据规模变化的函数，是算法效率分析的重要指标之一。通过分析时间复杂度，我们可以预估算法的运行时间，选择最优的算法来解决特定的问题。

1. 时间复杂度的概念

在计算机科学中，时间复杂度反映的是算法运行所需时间与输入规模之间的关系。通常用大O符号 (O) 来描述，例如 O(1)、O(n)、O(n log n) 等。常见的时间复杂度等级如下：

  • O(1): 常数时间复杂度，不受输入规模影响。
  • O(n log n): 对数时间复杂度，通常出现在二分查找等算法中。
  • O(n): 线性时间复杂度，算法的执行时间与输入数据规模成正比。
  • O(n log n): 线性对数时间复杂度，通常出现在高效排序算法中，如合并排序和快速排序。
  • O(n²): 平方时间复杂度，常见于简单的嵌套循环，如冒泡排序。
  • O(2^n): 指数时间复杂度，通常出现在递归算法中，尤其是解决组合问题时。
  • O(n!): 阶乘时间复杂度，常见于解决排序和排列问题的算法。

2. 时间复杂度的分析方法

此为重点，不然也不会考炸掉

（1） 基本操作

在分析时间复杂度时，我们通常关注算法中最基本的操作，例如赋值、比较和简单的数学运算。通过计算基本操作的执行次数，我们可以得到算法的总体时间复杂度。

（2） 最坏情况与平均情况

时间复杂度的分析通常会分别考虑最坏情况和平均情况。最坏情况时间复杂度描述的是在最不利情况下算法的执行时间，而平均情况时间复杂度则描述了在所有输入的情况下算法的平均执行时间。

（3）忽略低阶项和常数项

在表示时间复杂度时，通常采用约定：忽略低阶项和常数项（这词是从百度查来的），因为在输入规模较大时，低阶项和常数项对算法的效率影响较小。
举个栗子，如果一个算法对于任何大小为 n 的输入，它至多需要 5n^3 + 3n 的时间运行完毕，那么它的渐近时间复杂度是 O(n^3)。

3. C++代码示例

下面的示例展示了不同时间复杂度的算法如何在C++中实现。

（1） O(1) 示例

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	cout << "重生之窝在《xyd》学习基础算法3，PS：密涅瓦的猫头鹰老师好帅" ;
	
	return 0;
}

（2）O(n) 示例

#include <bits/stdc++.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cout << "蔡老师威武" << '\n'; 
	}
	
	return 0;
}

（3）O(n²) 示例

冒泡排序时间复杂度为O(n²)

#include <bits/stdc++.h>

using namespace std;

int a[10000005];

int main(void)
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = 1; j <= n - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a[j], a[j + 1]);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << a[i] << ' ';
    }

    return 0;
}

（4） O(n log n) 示例

以下是二分查找的模版，时间复杂度为O(n log n)

#include <bits/stdc++.h>

using namespace std;

int a[1000005];

int main(void)
{
	int n;
	cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	
	int m;
	while (cin >> m) {
		int l = 1;
		int r = n;
		while (l < r) {
			int mid = (l + r) >> 1;
			if (a[mid] >= m) r = mid;
			else l = mid + 1; 
		}
		if (a[l] == m) {
			cout << l << ' ';
		} else {
			cout << 0 << ' ';
		}
	}
	
	return 0;
}

4. 总结

时间复杂度是衡量算法效率的重要标准，理解不同时间复杂度对选择合适的算法至关重要。通过对算法的分析，我们可以在设计程序时做出明智的决策，优化性能。在实际编程过程中，选择合适的算法和数据结构可以显著提高程序的运行效率，特别是在处理大型数据集时。

二、 网址域名后缀

网址域名后缀（又称“顶级域名”或TLD，Top-Level Domain）是域名系统中最右边的一部分，例如在域名“https://www.xinyoudui.com/”中，“.com”就是顶级域名。顶级域名根据其类型和用途，可以分为几类，主要包括：

  1. 通用顶级域名（gTLD）：
  • .com：最常用的顶级域名，最初用于商业网站，现在几乎适用于任何类型的网站。
  • .org：通常用于非营利组织，但不限于此。
  • .net：最初用于网络服务提供商，现也适用于各种网站。
  • .info、.biz、.name等：提供特定用途的通用域名。
  1. 国家顶级域名（ccTLD）：
  • 这些域名专门为特定国家或地区设立，通常是两字母的国别代码，例如：
    • .cn（中国）
    • .us（美国）
    • .uk（英国）
  • 国家域名有时会被某些网站用于特定的市场定位。
  1. 新通用顶级域名（New gTLD）：
  • 自2013年起，互联网名称与数字地址分配机构（ICANN）开始引入新的通用顶级域名。这些包括：
    • .app：为应用程序相关的网站设计。
    • .guru、.vip、.club等：面向特定社群或兴趣的小众市场。
  1. 功能性顶级域名（Sponsored TLDs）：
  • 这些域名是为特定组织或社群所赞助和管理的，例如：
    • .edu：通常用于高等教育机构。
    • .gov：用于政府机构。
    • .mil：用于军事机构。

选择域名后缀时，应该考虑你的网站目标和受众。例如，如果你是一个商业网站，可以选择“.com”或“.biz”。如果你是非营利组织，可以考虑“.org”。如果你的业务面向特定国家或地区，使用对应的国家顶级域名可能会增加你的当地知名度。

三、图

图（Graph）是一种重要的数据结构，我们还没学，它由一组顶点（或节点，vertices）和一组边（edges）组成。图可以用来表示各种复杂的关系和结构，包括社交网络、交通网络、互联网和更多的应用场景。以下是图的基本概念和一些分类：

基本概念

  1. 顶点（Vertex）：
  • 图中的基本单元，代表某个对象或实体。例如，在社交网络中，顶点可以表示用户。
  1. 边（Edge）：
  • 连接两个顶点的线，表示它们之间的关系或连接。例如，在社交网络中，边可以表示用户之间的朋友关系。
  1. 边的类型：

  • 无向边（Undirected Edge）：边没有方向，表示两个顶点之间的双向关系。

  • 有向边（Directed Edge）：边有方向，表示一个顶点到另一个顶点的单向关系。

  1. 权重：
  • 边可以有权重（Weight），表示两个顶点之间的距离、成本或其他度量。例如，在地图中，边可以表示城市之间的距离。

图的分类

  1. 无向图（Undirected Graph）：
  • 所有边都是无向的。无向图中不存在边的方向。
  1. 有向图（Directed Graph）：
  • 至少有一条边是有方向的。图中的边从一个顶点指向另一个顶点。

    我只知道这两种，以下内容由百度赞助

  1. 加权图（Weighted Graph）：
  • 边可以有权重，表示边的成本或距离。
  1. 非加权图（Unweighted Graph）：
  • 所有边的权重相同，通常假设为1。
  1. 简单图（Simple Graph）：
  • 无向图或有向图中没有自循环和重复边。
  1. 多重图（Multigraph）：
  • 允许存在多条连接两个顶点的边。
  1. 完全图（Complete Graph）：
  • 每一对不同的顶点之间都有一条边。
  1. 连通图（Connected Graph）与强连通图（Strongly Connected Graph）：
  • 连通图：任意两个顶点之间存在路径。
  • 强连通图：有向图中的任意两个顶点都存在双向路径。
  1. 树（Tree）：
  • 一种特殊类型的无向图，是一种连通且无环的图。

图的表示方法

  1. 邻接矩阵（Adjacency Matrix）：
  • 使用二维数组表示顶点之间的边。若有边则数组元素为1（或权重），否则为0。

例如，图的邻接矩阵如下（无向图）：

A B C
A 0 1 0
B 1 0 1
C 0 1 0
  1. 邻接表（Adjacency List）：
  • 使用链表或数组列表表示每个顶点的邻接顶点。对于每个顶点，保存一个列表，其中存储与该顶点相邻的顶点。

例如，图的邻接表如下（无向图）：

A -> C
C -> A, W
W -> C

常用算法

图的许多算法用于解决特征问题，各种问题的解决方案也取决于图的结构。常见的算法包括：

  • 图的遍历：
    • 深度优先搜索（DFS）
    • 广度优先搜索（BFS）
      （有没有大佬告诉我下面是什么算法）
  • 最短路径问题：
    • Dijkstra算法
    • Bellman-Ford算法
    • Floyd-Warshall算法
  • 最小生成树：
    • Prim算法
    • Kruskal算法

图作为一种重要的数据结构，广泛应用于计算机科学及其相关领域，帮助我们解决复杂问题并建立更丰富的模型。

打字打了那么久

给个赞吧！！！

23 个赞
3

我嫉妒了，你的这个13个点赞，我的同类型才6个点赞…

3 个赞