算法和 运行-时间分析
algorithms and run-time analysis
一个文件（包括两个例子）是一个禁止号码区间的列表。例如，包含 12-18 的行表示禁止使用 12 到（含）18 的所有数字。间隔可能重叠。
我们想知道最小值是多少。
使用变量分析运行-时间（不一定需要全部）：
• N：最大（不是允许的最大）数量；所以数字在 0 和 N
之间
• K：文件中的间隔数
• M：最大区间宽度。
一个。有一个明显的方法可以解决这个问题：我们正在检查所有数字，直到我们 运行 进入允许的最小值。
• 这种算法有多快？
乙。您或许可以想象另一种使用 N 字节（或位）内存的简单算法。
（提示：删除线。）
• 用文字描述。例如，您可以进行自己的分配（比如一些介于 0 和 20 之间的数字间隔），并在其上显示算法。但是，它也起草了一般说明。
• 这个算法有多快？思考时，用N、K、M（如果你需要的话）。
C。做一个不额外消耗内存的算法（更准确的说：内存消耗应该与N、K、M无关），但是比A点下的算法要快。
• 形容它。
• 它有多快？是不是比B算法快？
D.现在我们感兴趣的是允许有多少个数字（0 到 N 之间）。对于这个问题，您将如何调整上述算法？他们的费率会怎样？
file = "0-19.txt"
intervals = [tuple(map(int, v.split("-"))) for v in open(file)]
#example# intervals = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]#
我当前的代码只是执行程序，但我还没有想出更好的代码算法，仍然需要大量工作才能理解，我需要一个快速解决方案 code/algorithm 例如 A、B、和C，也许还有D。然后我可以自己研究时间分析。感谢帮助！
def generator_intervala(start, stop, step):
forbidden_numbers = set()
while start <= stop:
forbidden_numbers.add(start)
start += step
return (forbidden_numbers)
mnozica = set()
for interval in intervals:
a, b = interval
values = (generator_intervala(a, b, 1))
for i in values:
mnozica.add(i)
allowed_numbers = set()
N = max(mnozica)
for i in range(N):
if i not in mnozica:
allowed_numbers.add(i)
print(intervals)
print(mnozica)
print(min(allowed_numbers))
print(max(mnozica))
Output:
[(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19}
10
19
您设置的方法不必要地复杂：
N = 100
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
do_not_use = set()
for (a,b) in ranges:
do_not_use.update(range(a,b+1))
print(do_not_use)
print( min(a for a in range(N+1) if a not in do_not_use))
几乎是所有需要的。输出：
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19])
10
这与 N 无关，它只取决于范围内有多少数字。
仅在集合中存储禁止数字需要 O(1) 进行检查，使用范围内的 min() 构建来获得最小值。
如果先对元组进行排序，然后对它们进行迭代，直到找到第一个间隙，排序时为 Θ(N log N)，然后为搜索时为 Θ(N)：
def findme():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
ranges.sort() # inplace sort, no additional space requirements
if ranges[0][0]>0:
return 0
for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
if a_max < b_min-1:
return a_max+1
return ranges[-1][1]+1 # might give you N+1 if no solution in 0-N exists
timeit 你的 vs 我的：
您的代码使用了 2 个集合，以及多个循环，增量添加到您的集合和函数调用中使其变慢：
N = 100
def findme():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
ranges.sort()
if ranges[0][0]>0:
return 0
for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
if a_max < b_min-1:
return a_max+1
return ranges[-1][1]+1
def mine():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
N = 100
do_not_use = set()
for (a,b) in ranges:
do_not_use.update(range(a,b+1))
return min(a for a in range(N+1) if a not in do_not_use)
def yours():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
def generator_intervala(start, stop, step):
forbidden_numbers = set()
while start <= stop:
forbidden_numbers.add(start)
start += step
return (forbidden_numbers)
mnozica = set()
for interval in ranges:
a, b = interval
values = (generator_intervala(a, b, 1))
for i in values:
mnozica.add(i)
allowed_numbers = set()
N = max(mnozica)
for i in range(N):
if i not in mnozica:
allowed_numbers.add(i)
return min(allowed_numbers)
import timeit
print("yours", timeit.timeit(yours,number=100000))
print("mine", timeit.timeit(mine,number=100000))
print("findme", timeit.timeit(findme,number=100000))
输出：
yours 1.3931225209998956
mine 1.263602267999886
findme 0.1711935210005322
一个文件（包括两个例子）是一个禁止号码区间的列表。例如，包含 12-18 的行表示禁止使用 12 到（含）18 的所有数字。间隔可能重叠。 我们想知道最小值是多少。 使用变量分析运行-时间（不一定需要全部）：
• N：最大（不是允许的最大）数量；所以数字在 0 和 N
之间• K：文件中的间隔数
• M：最大区间宽度。
一个。有一个明显的方法可以解决这个问题：我们正在检查所有数字，直到我们 运行 进入允许的最小值。 • 这种算法有多快？
乙。您或许可以想象另一种使用 N 字节（或位）内存的简单算法。 （提示：删除线。） • 用文字描述。例如，您可以进行自己的分配（比如一些介于 0 和 20 之间的数字间隔），并在其上显示算法。但是，它也起草了一般说明。 • 这个算法有多快？思考时，用N、K、M（如果你需要的话）。
C。做一个不额外消耗内存的算法（更准确的说：内存消耗应该与N、K、M无关），但是比A点下的算法要快。 • 形容它。 • 它有多快？是不是比B算法快？
D.现在我们感兴趣的是允许有多少个数字（0 到 N 之间）。对于这个问题，您将如何调整上述算法？他们的费率会怎样？
file = "0-19.txt"
intervals = [tuple(map(int, v.split("-"))) for v in open(file)]
#example# intervals = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]#
我当前的代码只是执行程序，但我还没有想出更好的代码算法，仍然需要大量工作才能理解，我需要一个快速解决方案 code/algorithm 例如 A、B、和C，也许还有D。然后我可以自己研究时间分析。感谢帮助！
def generator_intervala(start, stop, step):
forbidden_numbers = set()
while start <= stop:
forbidden_numbers.add(start)
start += step
return (forbidden_numbers)
mnozica = set()
for interval in intervals:
a, b = interval
values = (generator_intervala(a, b, 1))
for i in values:
mnozica.add(i)
allowed_numbers = set()
N = max(mnozica)
for i in range(N):
if i not in mnozica:
allowed_numbers.add(i)
print(intervals)
print(mnozica)
print(min(allowed_numbers))
print(max(mnozica))
Output:
[(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19}
10
19
您设置的方法不必要地复杂：
N = 100
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
do_not_use = set()
for (a,b) in ranges:
do_not_use.update(range(a,b+1))
print(do_not_use)
print( min(a for a in range(N+1) if a not in do_not_use))
几乎是所有需要的。输出：
set([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 12, 13, 14, 15, 16, 17, 18, 19])
10
这与 N 无关，它只取决于范围内有多少数字。
仅在集合中存储禁止数字需要 O(1) 进行检查，使用范围内的 min() 构建来获得最小值。
如果先对元组进行排序，然后对它们进行迭代，直到找到第一个间隙，排序时为 Θ(N log N)，然后为搜索时为 Θ(N)：
def findme():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
ranges.sort() # inplace sort, no additional space requirements
if ranges[0][0]>0:
return 0
for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
if a_max < b_min-1:
return a_max+1
return ranges[-1][1]+1 # might give you N+1 if no solution in 0-N exists
timeit 你的 vs 我的：
您的代码使用了 2 个集合，以及多个循环，增量添加到您的集合和函数调用中使其变慢：
N = 100
def findme():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
ranges.sort()
if ranges[0][0]>0:
return 0
for ((a_min,a_max),(b_min,b_max)) in zip(ranges,ranges[1:]):
if a_max < b_min-1:
return a_max+1
return ranges[-1][1]+1
def mine():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
N = 100
do_not_use = set()
for (a,b) in ranges:
do_not_use.update(range(a,b+1))
return min(a for a in range(N+1) if a not in do_not_use)
def yours():
ranges = [(12, 18), (2, 5), (3, 8), (0, 4), (15, 19), (6, 9), (13, 17), (4, 8)]
def generator_intervala(start, stop, step):
forbidden_numbers = set()
while start <= stop:
forbidden_numbers.add(start)
start += step
return (forbidden_numbers)
mnozica = set()
for interval in ranges:
a, b = interval
values = (generator_intervala(a, b, 1))
for i in values:
mnozica.add(i)
allowed_numbers = set()
N = max(mnozica)
for i in range(N):
if i not in mnozica:
allowed_numbers.add(i)
return min(allowed_numbers)
import timeit
print("yours", timeit.timeit(yours,number=100000))
print("mine", timeit.timeit(mine,number=100000))
print("findme", timeit.timeit(findme,number=100000))
输出：
yours 1.3931225209998956
mine 1.263602267999886
findme 0.1711935210005322