小编Cos*_*Cat的帖子

对于以下算法：

 int x = 0;
 for (int i = 0; i < n; i++)
     for (j = 0; j < n; j++) {
         if (j < i) j = j + n;
         else x = x + 1;
      }

因此，对于这种算法，我的思考过程如下：

内循环执行n对jwhen的迭代i=0。但是，对于的每个值i=0,1..n-1，j只会执行一次迭代，因为if语句的求值为true并结束内部循环。

这是我的困惑来源：

由于外循环n无论如何都将执行迭代，并且由于内循环会n在i=0（第一次迭代）时执行迭代，因此big-Oh时间复杂度不是O（n²），而是O（n），如果循环是嵌套的，并且都n在第一次迭代中执行迭代？

所以我一直在尝试打开这样的非常基本的文件：inputFile = open("keywords.txt", "r")

但我收到这个错误：

FileNotFoundError: [Errno 2] No such file or directory: 'keywords.txt'

这肯定是因为 Python 的默认工作目录不是我的 .py 文件所在的目录（如果我错了，请纠正我）。如何找到我正在工作的目录的确切路径，然后将Python的默认工作目录更改为它？

注意：我在OSX Mojave上使用VSCode和Anaconda (Python 3.6)

因此，在以下代码中，j执行n时间when i = 0。一旦i迭代一次(i = 0,2,3....n)，就j永远不会执行，因为if语句的条件为true并n添加到j。i继续迭代，直到n循环（两个循环）停止执行且方法结束为止。

public static void main(String[] args) {
        int x = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(j < i) j = j + n;
                else x = x+1;
            }
        }
    }

我的困惑在于，为什么时间复杂度是O(n)两个循环都迭代到n某个点，i总是迭代n并j迭代到n …

给定一个冒泡排序算法

for (int i = 0; i < A.length - 1; i++)
            for (int j = 0; j < A.length - i - 1; j++)
                if (A[j] > A[j + 1]) {
                    int temp = A[j];
                    A[j] = A[j + 1];
                    A[j + 1] = temp;
                }

如果给定的数组已经排序，则内部循环中的 if 语句将始终为 false，从而破坏内部 for 循环并递增j直到A.length-i-1到达。当A.length-i-1达到时，i增加。这个过程循环进行，直到i达到A.length-1。

我的困惑：

如果两个嵌套循环都迭代到各自的上限，尽管没有进行交换，但最佳情况下时间复杂度不是仍然是O(n^2)吗？谁能简单地向我解释一下为什么它会是O(n)