确定复杂性等级

Question

这里有什么重要的记号？一个解释将不胜感激.谢谢.

public static int[] mystery1(int[] list) {

  int[] result = new int[2 * list.length];
  for (int i = 0; i < list.length; i++) {
    result[2 * i] = list[i] / 2 + list[i] % 2;
    result[2 * i + 1] = list[i] / 2;
  }

  return result;

}

Answer 1

它是O(n),其中n是列表的长度.无论如何,您都要浏览整个列表.

算术运算的数量是:

• 2n次乘法
• 2n添加
• 2n分裂
• n模运算

这不计算实现for循环的算术运算.