算法和数据结构是计算机科学的基础。如果没有正确的算法和数据结构知识,开发人员将不得不经历艰难的情况,或者可能会保持业余水平。基本上,如果你应聘更大的公司,他们肯定会有算法和数据结构方面的面试问题。程序员的艺术是通过正确选择数据结构来实现最有效的算法。
简而言之,算法是解决问题的一系列规则,数据结构是你收集和组织数据的地方。无论是数据挖掘、机器学习、人工智能、Web 应用程序还是移动应用程序,你都应该熟悉算法和数据结构。
时间复杂度和运行时间为了了解算法的效率,我们需要熟悉解决特定问题所需的时间。通常,我们使用术语 Big O 表示法来衡量算法的时间复杂度。
所以,让我们用一些代码来解释它:
private void Print(int N){
for(int i=0;i<N;i ){
Console.WriteLine("hello world");
}
}
上面的代码将打印“hello world”N 次。所以,一般来说,你可以说上面程序的运行时间是 O(N),其中 O 是大 O 表示法。
我们再看一段代码:
int N = 5;
int count = 0;for (int i = 0; i < N; i )
{
for (int j = 0; j < N; j ){
Console.Write( count);
Console.WriteLine(".hello world");
}
}
上面的代码会打印 25 次“hello world”,也就是说上面算法的运行时间是 O(N²)。
以下部分描述了运行时间的时间复杂度。
1. 常数
运行时间:O(1)
执行给定操作需要固定数量的步骤。例如,1、5、10 或其他数字,并且此计数不依赖于输入数据的大小。Dictionary和hashmap是具有恒定时间复杂度的数据结构的示例。
2. 对数
运行时间:O (log(N))
它采用 log(N) 步骤的顺序,其中对数的底通常为 2,用于对 N 个元素执行给定的操作。如果 N=1,000,000,复杂度为 O(log(N)) 的算法将执行大约 20 步。
3.线性
运行时间:O(N), O(N*log(N))
对 N 个元素执行操作所需的步数几乎与元素数相同。如果 N=1,000,000,复杂度为 O(N) 的算法将执行大约 1,000,000 步。
如果 N=1,000,000,复杂度为 O(N*log(N)) 的算法将执行大约 1,000,000 * 20 步。
4.二次方
运行时间:O(N²)
它需要 N 平方步数。
5.立方
运行时间:O(N³)
它需要 N 立方步数。
6:指数
运行时间:O(2^N), O(N!), O(N^N)
它需要几个步骤,对输入数据具有指数可靠性。在 N=20 和 O(2^N) 的时间复杂度下,它需要 1,048,576 步。
时间复杂度和执行时间本节根据元素的数量描述时间复杂度及其执行时间。
如果复杂度低,即使对于大量元素,程序也会执行得很快;如果复杂度高,则对于少量元素,程序会执行缓慢甚至挂起。下表显示了时间复杂度及其执行时间。
了解你正在编写的程序的时间复杂度非常重要。
,