在《算法导论》第一部分练习中，有这样一道算法题： 1.2-3 对于一个运行时间为100n*n的算法，要使其在同一台机器上，在比一个运行时间为2^n的算法运行的很快，n的最小值是多少？...下面给出我自己的解题思路： 对于100n^2和2^n两个算法进行比较，我们可以这样做：对100n^2-2^n操作，如果结果小于0，那么此时的n就是我们所求的值。...-3：对于一个运行时间为100n^2的算法,要使其在同一台机器上,比一个运行时间为2^n的算 8 * 法运行得更快，n的最小值是多少？...100n^2和2^n两个算法进行比较，我们可以这样做：对100n^2-2^n操作，如果结果小于0，那么此时的n就是我们所求的值。...38 } 运行效果： 第1次计算结果为：98 第2次计算结果为：396 第3次计算结果为：892 第4次计算结果为：1584 第5次计算结果为：2468 第6次计算结果为：3536 第7次计算结果为：4772
当人们看到两个线性操作时，他们有时会认为结果是平方的，但是只有一个操作嵌套在另一个操作中才适用。如果你在一个操作之后调用另一个，运行时间会相加。如果它们都是O(n)的，则总和也是O(n)的。...你将使用Profiler，为 Java 的实现ArrayList和LinkedList，划分add方法的性能。...解释嘈杂的测量值的更好方法是，在重对数刻度上绘制的运行时间和问题规模。 为什么？我们假设运行时间与n ** k成正比，但是我们不知道指数k是什么。...其中重要的一点：如果你在图形看到这样的直线，这并不意味着该算法是线性的。如果对于任何指数k，运行时间与n ** k成正比，我们预计看到斜率为k的直线。如果斜率接近1，则表明算法是线性的。...你应该得到类似图 4.1 的结果，但是你可能需要调整startN或endMillis。估计的斜率应该接近1，表明执行n个添加操作的所需时间与n成正比；也就是说，它是O(n)的。
我们得出结论，执行n次添加是 O(n)的，所以平均来说，单个添加的时间是常数时间，或者O(1)，基于算法分析，这是我们的预期。...相反，如果对于任何指数k，运行时间与n ** k成正比，我们预计会看到斜率为k的直线。在这种情况下，我们预计，n次添加的总时间与n ** 2成正比，所以我们预计会有一条斜率为2的直线。...图 5.2：分析结果：在LinkedList末尾添加n个元素的运行时间和问题规模 同样，测量值很嘈杂，线不完全是直的，但估计的斜率为1.19，接近于在头部添加元素，而并不非常接近2，这是我们根据分析的预期...（头部） n 1 remove（一般） n n 5.5 结构的选择 对于头部插入和删除，双链表的实现优于ArrayList。...如果你知道，你的应用程序的运行时间取决于get和set元素的所需时间，则ArrayList可能是更好的选择。如果运行时间取决于在开头或者末尾附加添加和删除元素，LinkedList可能会更好。
} } 不管ArrayList还是LinkedList作为参数被传递，makeList1的运行时间都是O（N），因为对add的每次调用都是在表的末端进行从而花费常数时间（可以忽略对ArrayList...O（N），但是对于ArrayList其运行时间则是O（n^2），因为在ArrayList中，在前端进行添加是一个O（N）操作。...O（N），但对于LinkedList来说，其运行时间则是O（n^2），因为LinkedList中，对get的调用为O（N）操作。...i++; } } } 对于LinkedList来说，上面的解法运行时间则是O（n^2），使用迭代器的效率会更好，当然在使用迭代器时，我们不能直接使用List...而即使使用Iterator，ArrayList的remove方法还是O（n^2），因为删除，数组的数还是需要进行移动。
ArrayList没有同步。 size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 ...添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。...总结 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。 ...但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？...O(1)，但它在索引一个元素的使用缺比较慢－O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。
，ArrayList和LinkedList。...对于一些应用，LinkedList更快；对于其他应用，ArrayList更快。 要确定对于特定的应用，哪一个更好，一种方法是尝试它们，并看看它们需要多长时间。...常数时间：如果运行时间不依赖于输入的大小，算法是“常数时间”。例如，如果你有一个n个元素的数组，并且使用下标运算符（[]）来访问其中一个元素，则此操作将执行相同数量的操作，而不管数组有多大。...线性：如果运行时间与输入的大小成正比，则算法为“线性”的。例如，如果你计算数组的和，则必须访问n个元素并执行n - 1个添加。操作的总数（元素访问和加法）为2 * n -1，与n成正比。...所以如果操作总数为2 * n + 1，则属于O(n)。主要常数2和附加项1对于这种分析并不重要。与之类似，n ** 2 + 100 * n + 1000是O(n ** 2)的。不要被大的数值分心！
② LinkedList 采用链表存储，所以对于add(E e)方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置i插入和删除元素的话（(add(int index,...是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。...为什么呢？我觉得还是和底层数据结构有关！ArrayList 底层是数组，而 LinkedList 底层是链表。数组天然支持随机访问，时间复杂度为 O(1)，所以称为快速随机访问。...并且 采用二进制位操作 &，相对于%能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。...Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))） synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要
不可以根据元素的位置直接计算出内存地址，只能按顺序读取元素。读取一个特定位置元素的平均时间复杂度为O(n)。主要以链表为代表。Java中以LinkedList为代表。...所以我们可以知道，对于顺序存储，因为读取特定位置元素的平均时间复杂度是O(1)，所以遍历整个集合的平均时间复杂度为O(n)。...而对于链式存储，因为读取特定位置元素的平均时间复杂度是O(n)，所以遍历整个集合的平均时间复杂度为O(n2)（n的平方）。 ArrayList按位置读取的代码：直接按元素位置读取。 ?...类型的集合来说，没有太多意义，反而因为一些额外的操作，还会增加额外的运行时间。...，这样一来，遍历整个集合的时间复杂度就降低为O(n)； （这里只用LinkedList做例子）LinkedList的迭代器，内部实现，就是维护当前遍历的位置，然后操作指针移动就可以了：
此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。...ArrayList没有同步。size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 ...通过get(int index)获取ArrayList第index个元素时。直接返回数组中index位置的元素，而不需要像LinkedList一样进行查找。...(03) 对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。...(04) 对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
此外在LinkedList的首部或尾部提供额外的get、remove、insert方法。 这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。...size、isEmpty、get、set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间，其他的方法运行时间为线性。...如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个...但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除元素的索引位置。为什么会这样呢？...总结 如果涉及到堆栈、队列等操作，应该考虑用List； 对于需要快速插入，删除元素，应该使用LinkedList； 如果需要快速随机访问元素，应该使用ArrayList。
LinkedList 的时间复杂度 ①、由于 ArrayList 是基于数组实现的，所以 get(int index) 可以直接通过数组下标获取，时间复杂度是 O(1)；LinkedList 是基于链表实现的...，get(int index) 需要遍历链表，时间复杂度是 O(n)。...当然，get(E element) 这种查找，两种集合都需要遍历通过 equals 比较获取元素，所以时间复杂度都是 O(n)。...②、ArrayList 如果增删的是数组的尾部，直接插入或者删除就可以了，时间复杂度是 O(1)；如果 add 的时候涉及到扩容，时间复杂度会提升到 O(n)。...，因为二者增删的时间复杂度都是 O(n)，都需要遍历列表；而是体现在增删的效率上，因为 LinkedList 的增删只需要改变引用，而 ArrayList 的增删可能需要移动元素。
O(1)；LinkedList 是基于链表实现的，get(int index) 需要遍历链表，时间复杂度是 O(n)。...当然，get(E element) 这种查找，两种集合都需要遍历通过 equals 比较获取元素，所以时间复杂度都是 O(n)。...②、ArrayList 如果增删的是数组的尾部，直接插入或者删除就可以了，时间复杂度是 O(1)；如果 add 的时候涉及到扩容，时间复杂度会提升到 O(n)。...如果是在链表的头部插入或者删除，时间复杂度是 O(1)；如果是在链表的中间插入或者删除，时间复杂度是 O(n)，因为需要遍历链表找到插入位置；如果是在链表的尾部插入或者删除，时间复杂度是 O(1)。...，因为二者增删的时间复杂度都是 O(n)，都需要遍历列表；而是体现在增删的效率上，因为 LinkedList 的增删只需要改变引用，而 ArrayList 的增删可能需要移动元素。
书接上回，我们开启了Java集合部分的学习，今天我们就来看一下List，其中它的核心有两个，一个ArrayList，一个LinkedList，而ArrayList的使用频率在集合中至少排第二，可以和HashMap...[] array = new int[]{1, 2, 3}; 而ArrayList的底层是通过动态数组实现，长度动态可变，会自动扩容。...增加时间复杂度：添加一个元素（调用 add() 方法时）的时间复杂度最好情况为 O(1)，最坏情况为 O(n)。...删除时间复杂度：删除一个元素（调用 remove(Object) 方法时）的时间复杂度最好情况 O(1)，最坏情况 O(n)。...修改时间复杂度：修改一个元素（调用 set()方法时）与查询操作类似，可以直接根据索引来访问元素，时间复杂度为 O(1)。 注：最好和最快情况分别是在列别尾部操作和头部或中间操作的差距。
看了一些所谓大公司的JAVA面试问题，发现对于JAVA集合类的使用都比较看重似的，而自己在这方面还真的是所真甚少，抽空也学习学习吧。...ArrayList没有同步。 size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。...添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。...如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个...总结 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
对于一颗二叉查找树，所有的信息都是有序排列的，中序遍历可以是信息有序输出，且运行时间为O（n）。...9 3 6 4 8 后序遍历 先处理左右子树，然后再处理当前节点，运行时间为O（n）。...好吧，下边厉害的要来了 层序遍历 层序遍历:所有深度为D的节点要在深度为D+1的节点之前进行处理，层序遍历与其他类型的遍历不同的地方在于它不是递归地执行的，它用到队列，而不使用递归所默示的栈。...层序遍历代码： package Tree;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import...ArrayList()); Queue queue = new LinkedList(); queue.add
看了一些所谓大公司的Java面试问题，发现对于JAVA集合类的使用都比较看重似的，而自己在这方面还真的是所真甚少，抽空也学习学习吧。...ArrayList没有同步。 size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。 ...添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。...如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个...总结 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。...有size，isEmpty，get，set方法，运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。...添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。...如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个...总结 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
此外LinkedList提供额外的get，remove，insert方法在LinkedList的首部或尾部。...ArrayList没有同步。 size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。...添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。...如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个...总结 如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
