时间戳

首页 > 解决方案 > 以下哪种方法更有效

arrays - 以下哪种方法更有效

问题描述

问题陈述：-给定一个整数数组和一个整数 k，打印数组中总和为 k 的所有对

方法1：- 对数组进行排序并保持两个指针低和高，开始迭代......

时间复杂度 - O(nlogn)

空间复杂度 - O(1)

方法2：- 保留字典中的所有元素并执行该过程

时间复杂度 - O(n)

空间复杂度 - O(n)

现在，在上述两种方法中，哪一种是最有效的，在这种情况下我将在什么基础上比较效率、时间（或）空间，因为这两种方法都不同

标签： arraysdata-structurestime-complexitybig-ospace-complexity

解决方案

  1. 我在上面留下了我的评论以供参考。
  2. 这很仓促。您确实为方法 1 排序留出了 O(nlogn) 时间（我现在想我明白了吗？），这很公平（道歉；-）。
  3. 接下来发生什么？如果必须再次使用输入数组，那么您需要一个排序副本（排序不会就地），这会增加 O(n) 空间要求。
  4. 方法 1 的“迭代”部分也需要 ~O(n) 时间。
  5. 但是在方法 2 中加载字典也是 ~O(n) 时间（可能是一次性的数据结构？）并且字典访问 - 尽管 ~O(1) - 比数组索引要慢。

底线：如果 O-notation 可以识别“压倒性成本”（通过比较使其他成本可以忽略不计），但没有提示用例（典型和边界，数据量和可用系统资源等细节），问题像这样（寻求“广义的理想”答案）不能从中受益。

通常，一些简单的概念验证代码和对代表性数据的性能测试可以使“正确的选择显而易见”（比推测理论更容易且通常更正确）。

最后，在没有明确的性能赢家的情况下，总是有“代码可读性”来帮助决定；-)

推荐阅读