我相信这个算法是O(N).我对么？

Question

该算法反转N个整数的数组.我相信这个算法是O(N),因为对于每个循环迭代,四行代码执行一次,从而在4N时间内完成作业.

public static void reverseTheNumbers(int[] list) {
    for (int i = 0; i < list.length / 2; i++) {
        int j = list.length - 1 - i;
        int temp = list[i];
        list[i] = list[j];
        list[j] = temp;
    }
}

Answer 1

没有4N时间这样的东西.该算法是线性的,因为随着您增加输入的大小,算法的运行时间会按比例增加.换句话说,如果你的大小加倍,list你会期望算法花费两倍的时间.

在循环中执行的操作数无关紧要 - 只要它们是每个常量时间(相对于输入),循环的运行时间仅由迭代次数决定.

换句话说,这四个陈述 - 一起 - 是O(1)操作.

int j = list.length - 1 - i;
int temp = list[i];
list[i] = list[j];
list[j] = temp;

在Java语法中用四个语句表示这一系列步骤这一事实没有什么重要意义 - 试验javap表明这四行编译成~20字节码命令,谁知道字节码被转换成多少处理器指令.好消息是,无论特定语法如何,Big-O表示法的工作方式都相同 - 如果执行时间与输入无关,则操作序列为O(1)或恒定时间.

因此,您正在进行N次操作O(1); 又名O(N).