该代码包含两个循环的时间复杂性是多少？

发布于 2025-01-29 00:31:17 字数 987 浏览 0 评论 0原文

这是Leetcode上的解决方案之一。

问题：鉴于每天收入的一系列，以及公司想要达到的一系列里程碑，返回包含公司每一个里程碑的日子的阵列。

输入收入是一个长度N阵列，代表每天（从第1天到N一天）的收入公司的收入。里程碑是总收入里程碑的长度K阵列。输出返回一个长度K阵列，其中k_i是公司首先获得里程碑的一天[i]总收入。如果从未达到里程碑，请返回-1。示例

revenues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
milestones = [100, 200, 500]
output = [4, 6, 10]

说明在第4、5和6天，公司的总收入分别为100美元，150美元和210美元。第6天是该公司首次获得总收入的200美元。

他们说，复杂性是o（klogk） + o（n），但由于有两个循环，一个o（n）复杂性的循环，也不是o（n）的一个循环，所以不应该是o（n^ 2） + o（klogk）？如果不是，为什么while循环不是o（n）？

def getMilestoneDays(revenues, milestones):
  ret = [len(revenues)]*len(milestones)
  milestones = sorted([(x,i) for i,x in enumerate(milestones)]) #O(klogk)
  sums = i = 0 # sums is the current cumulative sum of revenues, i is the current index of sorted milestones
  
  for j,x in enumerate(revenues, start=1): #O(n)
    sums+=x
    while i<len(milestones) and sums>=milestones[i][0]:
      ret[milestones[i][1]] = j
      i+=1
  return ret

原文

This is one of the solutions on LeetCode.

The problem:
Given an array of the revenue on each day, and an array of milestones a company wants to reach, return an array containing the days on which the company reached every milestone.

Input
revenues is a length-N array representing how much revenue company made on each day (from day 1 to day N). milestones is a length-K array of total revenue milestones.
Output
Return a length-K array where K_i is the day on which company first had milestones[i] total revenue. If the milestone is never met, return -1.
Example

revenues = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
milestones = [100, 200, 500]
output = [4, 6, 10]

Explanation
On days 4, 5, and 6, company has total revenue of $100, $150, and $210 respectively. Day 6 is the first time that the compnay has >= $200 of total revenue.

They said the complexity is O(klogk) + O(n) but since there are two loops, a for loop of O(n) complexity and a while loop also of O(n), shouldn't it be O(n^2) + O(klogk) instead? If not, why the while loop isn't O(n)?

def getMilestoneDays(revenues, milestones):
  ret = [len(revenues)]*len(milestones)
  milestones = sorted([(x,i) for i,x in enumerate(milestones)]) #O(klogk)
  sums = i = 0 # sums is the current cumulative sum of revenues, i is the current index of sorted milestones
  
  for j,x in enumerate(revenues, start=1): #O(n)
    sums+=x
    while i<len(milestones) and sums>=milestones[i][0]:
      ret[milestones[i][1]] = j
      i+=1
  return ret

分享到QQ

分享到微博