标签: little-o

Big-O表示法O(n)和Little-O表示法有o(n)什么区别？

我的一位同事问了我一个问题:那套o(1)(小符号)是空的吗？

我的问题是:是o(1)空集吗？如果没有,是否有一个o(1)时间复杂的程序？

提醒,科尔曼对小o的定义:

一个函数f(n)被说成是o(g(n))如果任何利好不断c>0,存在常数n0 > 0,使得0 <=f(n) < cg(n)对所有n>= n0.

直观地说,如果f(n)是o(g(n))如果是O(g(n)),但这种结合不紧.

我刚刚从一家公司接受了面试测试,我轻松地完成了它,但他们说我的功能是在o(n).这是问题所在

使用以下方法编写IntegerTracker类:

track(int) - Receives an integer for tracking. 
get_max() - Returns the max (int) of all integers seen so far. 
get_min() - Returns the min (int) of all integers seen so far. 
get_mean() - Returns the mean (float) of all integers seen so far.
get_mode() - Returns the mode (int) of all integers seen so far.

确保每个方法(包括跟踪)以恒定时间运行(O(1)时间复杂度).

这就是我完成它的方式

- (instancetype)init{
    if(self == [super init]){
        self.numbers = [[NSMutableArray alloc]init];
    }
    return self;
}

- (void)trackInt:(int)number{
    [self.numbers addObject:[NSNumber numberWithInt:number]];
}

- …