浅谈数据结构与算法&复杂度(object-C)
常用经典算法与数据结构目录如下
可以关注一下博客：http://www.cnblogs.com/mjios
Q：什么是数据结构？
常用数据结构如下
举例：
Q：什么是算法？
说明：算法是用于解决特定问题的一系列执行步骤
例如：
使用不同算法，解决同一个问题，效率可能相差非常大。
比如：求第n个斐波那契数（fibonacci number）
有俩种解决方案 1个是递归，一个是计算
当我们使用低轨来计算基本上到了50以上时间消耗会非常长，说明算法的性能并不好。反之用第二种思路时间消耗则非常短。也就是验证了，使用不同算法，解决同一个问题，效率可能相差非常大。
Q：那么我们该如何评判一个算法的好坏呢？？？
A：在保证正确性，可读性，健壮性的前提下时间复杂度与空间负载度越小越好。
那如何计算一个算法的时间复杂度呢？我们引入了一个概念叫大O表示法。
大O表示法对底数的处理：
常见的复杂度
复杂度练习（一般多讨论时间复杂度）：
/*
public static void test1(int n) {
// 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 1 + 4 + 4 + 4
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
// 时间复杂度： 14个指令 -》按照大O表示法忽略常数，系数，低阶 = O(1)
／／空间复杂度 ：= O(1)
}
public static void test2(int n) {
// 1 + 3n
for (int i = 0; i < n; i++) {
System.out.println("test");
// 时间复杂度：按照大O表示法忽略常数，系数，低阶 = O(n)
／／空间复杂度 ：= O(1)
}
}
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// 时间复杂度：按照大O表示法忽略常数，系数，低阶 =O(n^2)
／／ 空间复杂度：O（n）
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// 时间复杂度：按照大O表示法忽略常数，系数，低阶 = O(logn)
／／ 空间复杂度：空间复杂度：O（1）
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 3 * nlog2(n)
// 时间复杂度： 按照大O表示法忽略常数，系数，低阶 O(nlogn)
／／空间复杂度：O（n）
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test10(int n) {
// 空间复杂度：O(n)
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
*/
ok 接下来我们做一下之前我们做过的递归fib方法的复杂度分析
算法的优化方向在哪里呢？
另外多个数据规模的计算要注意
到这里相信大家对数据结构与算法中的算法和复杂度有初步的概念了。
更多复杂度知识在后续文章中在跟各位介绍：
最好，最坏复杂度
均摊复杂度
复杂度震荡
平均复杂度
最后给大家推荐一下练习算法题的网站
