S*********n
发帖数: 92 | 1 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
2. What is the difference between a map, a vector, and an array. Name a
situation for which each is uniquely well-suited.
多谢多谢！ | m*********2
发帖数: 701 | 2 靠， 啥问题。。。
f(n) = O(n log(n))
f(n) = ω(1)
map is a dictionary
vector is more generic array.
f(n) can be
f(n) =
【在 S*********n 的大作中提到】
: 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
: bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
: O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
: 2. What is the difference between a map, a vector, and an array. Name a
: situation for which each is uniquely well-suited.
: 多谢多谢！
| P**l
发帖数: 3722 | 3 第一题yes
第二题map跟后面那两没啥关系吧。区别是没顺序？
vector跟array有啥区别不知道。是不是应该跟不同语言/库的实现有关啊
(n) can be
n) =
【在 S*********n 的大作中提到】
: 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
: bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
: O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
: 2. What is the difference between a map, a vector, and an array. Name a
: situation for which each is uniquely well-suited.
: 多谢多谢！
| c****p
发帖数: 6474 | 4 个人观点：
map应该区别在支持多关键字查询。
比方说有这么个class
{
string name;
int gender;
int age;
....
} person;
如果用vector/array的话按名字查某个人只能用index/iterator来挨个看person.name。
map可以把name做成key，按名字查找方便很多。——看起来map更适合数据库方面的应用
。
以C++ STL，vector应该是array的超集：
共同点：两者都支持随机存储(random indexed access)
不同点：vector支持O(1)代价的元素的增删，array仅能“有限”地支持删。
因此，vector的实现代价也毫无疑问地比array大。
vector更适用于需要频繁变换数据集大小的场合，
array更适用于数据集大小固定，并且资源/性能要求严格的场合（或者没有C++ STL支持
的场合，比如说OS kernal/嵌入式？）。
【在 P**l 的大作中提到】
: 第一题yes
: 第二题map跟后面那两没啥关系吧。区别是没顺序？
: vector跟array有啥区别不知道。是不是应该跟不同语言/库的实现有关啊
:
: (n) can be
: n) =
| c****p
发帖数: 6474 | 5 第二题做个类似于accumulative sum的数组就可以了吧。。
S[n] = x0 + x1 + ... + xn
建S[n]是O(n)，而且是一遍lookup。
Cb(t) = S[t] - S[t-2];
Ca(t)应该类似。
for
and then the least significant digits. For example, {254, 257, 322} →{322,
254, 257}→{322, 257, 254}. What is the complexity of radix sort? In what
settings would radix sort be
【在 S*********n 的大作中提到】
: 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
: bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
: O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
: 2. What is the difference between a map, a vector, and an array. Name a
: situation for which each is uniquely well-suited.
: 多谢多谢！
| j*******r
发帖数: 52 | 6 vector和array区别可以回答数据类型吧。
vector可以装对象，大小动态可调，array只能装基本数据类型，大小固定。 | c****p
发帖数: 6474 | 7 array也可以装指向struct的指针
【在 j*******r 的大作中提到】
: vector和array区别可以回答数据类型吧。
: vector可以装对象，大小动态可调，array只能装基本数据类型，大小固定。
| g**e
发帖数: 6127 | 8 你把作业题拿上来问，合适吗？
for
and then the least significant digits. For example, {254, 257, 322} →{322,
254, 257}→{322, 257, 254}. What is the complexity of radix sort? In what
settings would radix sort be
【在 S*********n 的大作中提到】
: 1. Recall Big O notation. A function is equal to O(g(n)) if its runtime, f(n) can be
: bounded by g(n). That is, g(n) is “at least as bad” as f(n). Consider f(n) =
: O(log(n!)). Does f(n) = O(n log(n))? Does f(n) = ω(1)? Ω(1)?
: 2. What is the difference between a map, a vector, and an array. Name a
: situation for which each is uniquely well-suited.
: 多谢多谢！
| m*********2
发帖数: 701 | 9 re:
Undergraduate Algorithm class 的作业。
妈的
→{322,
【在 g**e 的大作中提到】
: 你把作业题拿上来问，合适吗？
:
: for
: and then the least significant digits. For example, {254, 257, 322} →{322,
: 254, 257}→{322, 257, 254}. What is the complexity of radix sort? In what
: settings would radix sort be
| j*******r
发帖数: 52 | 10 内存中struct XXX * 和 void * 没区别。。。
【在 c****p 的大作中提到】
: array也可以装指向struct的指针
| S*********n
发帖数: 92 | |
|
